Thuật toán số nguyên tố

Question

Bất cứ ai có thể cho tôi biết cách thực hiện thuật toán Sieve of Eratosthenes trong C? Tôi cần tạo số nguyên tố nhưng thuật toán của tôi chậm.

Mã của tôi:

#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 là số kiểm tra trường hợp m và n là phạm vi giữa mà thủ sẽ được in ra.

Answer 1

Bạn cần phải tạo một mảng các boolean lớn như số nguyên tố tối đa bạn muốn tìm. Lúc đầu nó hoàn toàn khởi tạo thành sự thật.

i ô thứ hai của mảng đó sẽ đúng nếu i là số nguyên tố hoặc sai nếu không.

Bắt đầu lặp lại từ i=2: số nguyên tố, sau đó đặt thành false bất kỳ ô nào có chỉ số nhiều là 2. Đi tới số nguyên tố tiếp theo (i=3) và thực hiện tương tự. Chuyển đến nguyên tố tiếp theo (đó là i=5: i=4 không phải là số nguyên tố: array[4] được đặt thành false khi đang xử lý i=2) và thực hiện lại như vậy một lần nữa.

Answer 2

Liên kết của Marc B hiển thị một thuật toán đơn giản và tốt đẹp, chính xác, được viết bởi NSLogan. Tôi đã viết một sửa đổi nhỏ cho nó để hiển thị một số kích thước/tốc độ cân bằng. Tôi nghĩ tôi sẽ chia sẻ vì lợi ích.

Thứ nhất, mã:

#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; 
} 

(Hãy tha thứ được thông báo lỗi vì không chính xác khi USE_BITS được định nghĩa ...)

Tôi đã so sánh ba cách khác nhau để lưu trữ các biến boolean peoro gợi ý. Một phương pháp thực sự sử dụng bit, thứ hai lấy toàn bộ byte, và phương thức cuối sử dụng toàn bộ từ máy. Một dự đoán ngây thơ về cái nào là nhanh nhất có thể là phương pháp từ máy, vì mỗi cờ/boolean được xử lý nhiều hơn một cách tự nhiên bởi máy của bạn. Timings để tính toán số nguyên tố lên đến 100.000.000 trên máy tính của tôi như sau:

Bits: 3.8s Chars: 5.8s M-chữ: 10.8s

Thật thú vị khi lưu ý rằng ngay cả xấu xí bit-shifting cần thiết để đại diện cho một boolean chỉ với một bit vẫn còn nhanh hơn tổng thể. Giả thuyết của tôi là bộ nhớ đệm và địa phương-tham chiếu dường như lớn hơn thêm ~ 3 hướng dẫn. Thêm vào đó, bạn sẽ sử dụng 1/nth bộ nhớ của phương pháp n-bit-machine-word!

Answer 3

Theo tôi, thuật toán của bạn chậm vì bạn tính số không cần thiết. thử mã này

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

Mặc dù nó là bài rất cũ, Sau đây là cố gắng của tôi để tạo ra các số nguyên tố sử dụng "Sieve of Eratosthenes" thuật toán.

#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]); 
    } 
    } 

} 

Hy vọng điều này sẽ giúp ai đó.

Answer 5

Đây thực sự là mã rất đơn giản sử dụng thuật toán Sieve of Eratosthenes. hoạt động cho tất cả các tích cực int.

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