소수의 나열, 시간복잡도, 공간복잡도

ver1.c

#include <stdio.h>
 
int main(void)
{
    int i, n;
    unsigned long counter = 0; //나눗셈 횟수
    for (n = 2; n <= 1000; n++) {
        for (i = 2; i < n; i++) {
            counter++;
            if (n%i == 0)
                break;
        }
        if (n == i)
        {
            printf("%d\n", n);
        }
    }
    printf("나눗셈을 실행한 횟수:%lu\n", counter);
 
    return 0;
}

 

ver2.c

소수 배열 저장

저장된 소수로 나누기

바깥 for문 n 값 2씩 증가해서 홀수값만 생성, 4이상의 짝수는 2로 나누어 떨어지기 때문

#include <stdio.h>
 
int main(void)
{
    int i, n;
    int prime[500]; //소수를 저장하는 배열
    int ptr = 0; //이미 얻은 소수의 개수
    unsigned long counter = 0; //나눗셈 횟수
    prime[ptr++] = 2; // 2는 소수.
 
    for (n = 3; n <= 1000; n += 2) {  //홀수만을 대상으로 한다. 4이상의 짝수는 2로 나누어 떨어지기 때문
 
        for (i = 1; i < ptr; i++) { // 이미 얻은 소수로 나눕니다.
            counter++;
            if (n%prime[i] == 0) //나누어 떨어지므로 소수가 아님
                break; 
        }
        if (ptr == i)
            prime[ptr++] = n;
    }
 
    for (i = 0; i < ptr; i++)
        printf("%d\n", prime[i]);
 
    printf("나눗셈을 실행한 횟수 %lu", counter);
        
}