소수 번호 알고리즘

Question

누구나 C에서 Sieve of Eratosthenes 알고리즘을 구현하는 방법을 알려주시겠습니까? 소수를 생성해야하지만 알고리즘이 느립니다.

내 코드 :

#include <stdio.h> 

int prime(long int i) 
{ 
    long int j; 
    int state = 1; 
    for(j=2;j<i;j++) 
    { 
     if((i%j)==0){state=0;break;} 
    } 
    return state; 
} 

int main() 
{ 
    int t; 
    long int m,n,i; 
    scanf("%d", &t); 
    while(t--) { 
     scanf("%d %d", &m,&n); 
     for(i=m;i<=n;i++) 
     { 
      if(i==1){ 
       //do nothing for 1 
      } else{ 
       if(prime(i))printf("%d\n",i); 
      } 
     } 
    } 
    return 0; 
} 

t 테스트 케이스 m의 개수이고, n이 인쇄되어야하는 소수의 사이의 범위이다.

Answer 1

찾으려는 최대 소수만큼 큰 부울 배열을 만들어야합니다. 처음에는 완전히 사실로 초기화되었습니다.

i이 소수 일 경우 해당 배열의 i 셀이 참이되고 그렇지 않으면 false가됩니다.

i=2에서 반복을 시작하십시오. 인덱스의 배수가 2 인 셀을 모두 거짓으로 설정하고 다음 소수 (i=3)로 이동하십시오. 다음 소수로 가십시오 (i=5 : i=4은 소수가 아닙니다 : i=2을 처리하는 동안 array[4]을 false로 설정 함). 몇 번이고 반복하십시오.

Answer 2

마크 B의 링크는 NSLogan이 작성한 정확하고 멋진 간단한 알고리즘을 보여줍니다. 나는 약간의 크기/속도 절충을 보여주기 위해 약간의 수정을했다. 나는 관심사로 나눌 줄 알았다.

우선, 코드 :

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <assert.h> 
#include <time.h> 

#define USE_BITS 

#ifdef USE_BITS 
#define alloc_prime char *prime = calloc(i/8,sizeof(*prime)); 
#define set_not_prime(x) prime[x/8]|= (1<<(x%8)) 
#define is_prime(x) (!(prime[x/8]&(1<<(x%8)))) 
#endif 

#ifdef USE_CHAR 
#define alloc_prime char *prime = calloc(i,sizeof(*prime)); 
#define set_not_prime(x) prime[x] = 1 
#define is_prime(x) (prime[x] == 0) 
#endif 

#ifdef USE_SIZE_TYPE 
#define alloc_prime size_t *prime = calloc(i,sizeof(*prime)); 
#define set_not_prime(x) prime[x] = 1 
#define is_prime(x) (prime[x] == 0) 
#endif 


int main(){ 
    int i; 
    printf("Find primes up to: "); 
    scanf("%i",&i); 

    clock_t start, stop; 
    double t = 0.0; 

    assert((start = clock())!=-1); 

    //create prime list 
    alloc_prime; 
    int c1, c2, c3; 
    if(!prime){ 
    printf("Can't allocate %zu bytes!\n",i*sizeof(*prime)); 
    exit(1); 
    } 

    //set 0 and 1 as not prime 
    set_not_prime(0); 
    set_not_prime(1); 

    //find primes then eliminate their multiples (0 = prime, 1 = composite) 
    for(c2 = 2;c2 <= (int)sqrt(i)+1;c2++){ 
    if(is_prime(c2)){ 
     c1=c2; 
     for(c3 = 2*c1;c3 <= i+1; c3 += c1){ 
     set_not_prime(c3); 
     } 
    } 
    } 

    stop = clock(); 
    t = (double) (stop-start)/CLOCKS_PER_SEC; 

    //print primes 
    for(c1 = 0; c1 < i+1; c1++){ 
     if(is_prime(c1))printf("%i\n",c1); 
     //  if(prime[c1] == 0) printf("%i\n",c1); 
    } 
    printf("Run time: %f\n", t); //print time to find primes 

    return 0; 
} 

은 (USE_BITS 정의 할 때 정확한 없었던 오류 메시지 용서 ...)

I 부울 변수를 저장하는 세 가지 방법을 비교 했으므로 peoro가 제안했다. 한 가지 방법은 실제로 비트를 사용하고, 두 번째 방법은 전체 바이트를 사용하고 마지막 방법은 전체 기계 단어를 사용합니다. 각각의 flag/boolean이 여러분의 머신에 의해 더 자연스럽게 다루어지기 때문에 가장 빠른 것에 대한 순진한 추측은 머신 워드 방식 일 것입니다. 내 컴퓨터이었다에 다음과 같이 타이밍은 100,000,000까지 소수를 계산 :

비트 : 3.8s 숯을 : 5.8S M-단어 : 10.8s

그 추악한도 모두 흥미 롭다 하나의 비트만으로 부울을 나타내는 데 필요한 비트 시프 팅은 전체적으로 더 빠릅니다. 나의 추측은 캐싱과 locality-of-reference가 여분 ~ 3 지시를 능가하는 것 같다. 또한, n-bit-machine-word 방식의 메모리의 1/nth를 사용하게됩니다!

Answer 3

내 의견으로는, 귀하의 필수 알고리즘을 계산할 때 알고리즘 속도가 느려집니다. 아주 오래된 포스트 비록 다음,이 코드를

int isPrime(int number){ 

    if(number < 2) return 0; 
    if(number == 2) return 1; 
    if(number % 2 == 0) return 0; 
    for(int i=3; (i*i)<=number; i+=2){ 
     if(number % i == 0) return 0; 
    } 
    return 1; 

} 

Answer 4

을 시도하는 것은 알고리즘을 "에라토스테네스의 체"를 사용하여 소수를 생성하는 나의 시도이다.

#include <stdio.h> 

#define NUM 8000  /* Prime Numbers in the Range. 'Range + 2' actually. */ 

int main() 
{ 
    int a[NUM] = {0};   /* Array which is going to hold all the numbers */ 
    int i , j; 

    /* initializing array from 2 to given number + 2, assuming the first prime number is 2 */ 
    for(i = 2,j=0; i < NUM+2, j<NUM; i++, j++) 
    { 
    a[j] =i; 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    int num = a[i]; 

    /* If number is not 0 then only update the later array index. */ 
    if(num != 0) 
    { 
     for (j = i+1; j < NUM; j++) 
     { 
     if((a[j]%num == 0)) 
     { 
      a[j]=0; 
     } 
     } 
    } 
    } 


    for(i = 0; i < NUM; i++) 
    { 
    /* Print all the non Zero *Prime numbers* */ 
    if(a[i] != 0) 
    { 
     printf("%d \n", a[i]); 
    } 
    } 

} 

희망이 있으면 도움이 될 것입니다.

Answer 5

에라 토 스테 네스 체의 알고리즘을 사용하는 실제로는 매우 간단한 코드입니다. 모두 긍정적 인 결과를 보입니다. int.

int is_prime(int n){ 
    int p; 
    for(p = 2; p < n; p++){ 
    if(n % p ==0 && p != n) 
     return 0;  
    } 
    return 1; 
}