첫 번째 소수 번호 최적화

Question

나는 인수에 관련된 질문을 이미 많이 보았지만 아무도 완벽하게 일치하지 않는 한 새 질문을하고 있습니다. 첫 번째 N 소수 (예에서는 1000)를 계산해야합니다. 내가 잘 작동하는 작동하는 알고리즘으로 나왔지만 전혀 최적화되지 않았습니다.

#include<stdio.h> 
#define MAX_NUMBERS 1000 
int main() 
{ 
    int prime[MAX_NUMBERS]={0}; 
    int filled=0; 
    prime[filled++]=2; 
    int n=0,i=0; 
    while(filled<MAX_NUMBERS) { 
     for(n=prime[filled-1]+1; ;n++) { 
     int found =0; 
     for(i=0; i<filled && (found==0); i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
      } 
     } 
     if(!found) { 
      break; 
     } 
     } 
     /* we know that this always exists */ 
     prime[filled++]=n; 
    } 
    for(i=0;i<filled;i++) { 
     printf("prime number %d\n", prime[i]); 
    } 
    return 0; 

}

사람이 최적화 할 수있는 방법을 생각을 가지고 있습니까? 이 경우 도움이 될 수있는 알고리즘 변경이 있습니까?

Answer 1

수행되는 루프 수를 줄이려면 소스 코드에 작은 소수 표를 저장할 수 있습니다.

또 다른 작은 최적화는 3보다 큰 소수는 모두 6k-1 또는 6k + 1의 형식이라는 사실에 기반합니다. 따라서 매 6 개의 홀수 중 3 개의 홀수를 확인하는 대신에 소수 만 2 개만 검사하면됩니다. Sieve of Eratosthenes, Sieve of Atkin, Sieve of Sundaram :

그러나 소수를 찾을 수있는 더 좋은 방법은 위에서 언급 한 바와 같이 체의 어떤 종류를 사용하는 것입니다.

Answer 2

당신은 당신이 그것보다 적은 숫자로 나누어 여부를 알고 그 광장보다 큰 숫자를 확인 할 필요가 없기 때문에 나는 sqrt(filled)을 사용

for(i = 0; prime[i] <= sqrt(n); i++) {...} 

을 수행하여 루프의 당신의 수를 줄일 수 있습니다 (1 제외).

Answer 3

int found =0; 
     for(i=0; i<filled && (found==0); i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
      } 
     } 
     if(!found) { 
      break; 
     } 

변경 (헤더 '포함하는 것을 잊지 마세요)이에 :

int found =0; 
     for(i=0; i < filled && prime[i]*prime[i]<=n; i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
       break; 
      } 
     } 
     if(!found) { 
      break; 
     } 

Answer 4

할 수있는 가장 좋은 방법은 가장 쉽고 매우 효율적 다음의 존재와 같은 체질의 방법을 통해 : -

Sieve of eratosthenes