Asal Sayı Algoritması

Question

Kimse C de Sieve of Eratosthenes algoritmasının nasıl uygulanacağını söyleyebilir mi? Asal sayıları üretmem gerekiyor ama algoritmam yavaş.

My kodu:

#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 test durumları sayısı m ve n, basılacak olan asal arasındaki aralıktır.

Answer 1

Bulmak istediğiniz maksimum asal sayı kadar büyük bir boole dizisi oluşturmanız gerekir. Başlangıçta tamamen doğru olarak başlatıldı.

i, bu tür bir dizinin i th hücresi bir asal sayı veya doğru değilse, yanlış olur.

i=2'dan yinelenen başlatmaya başlayın: daha sonra, 2'nin bir indeksi birden fazla olan herhangi bir hücreyi false olarak ayarlayın. Sonraki asal sayıya (i=3) gidin ve aynısını yapın. Bir sonraki konuya git (i=5: i=4 asal değil: , i=2 işlenirken yanlış olarak ayarlandı) ve aynı işlemi tekrar tekrar yapın.

Answer 2

Marc B's linki, NSLogan tarafından yazılmış, doğru ve güzel bir algoritma göstermektedir. Bazı boyut/hız değişimlerini göstermek için ufak bir değişiklik yaptım. Faiz için paylaşacağımı düşündüm.

Öncelikle kod:

#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 tanımlandığında doğru olmadığı için hata mesajı affedin ...)

Ben boolean değişkenler depolamak üç farklı yollar karşılaştırıldığında ettik peoro önerdi. Bir yöntem aslında bit kullanır, ikincisi tüm bayt alır ve son olarak tüm makine kelimesini kullanır. En hızlı olanı tahmin eden saf bir tahmin, makine kelimesi metodu olabilir çünkü her bayrak/boole, makineniz tarafından daha 'doğal olarak' ele alınır. Benim makine vardı üzerinde aşağıdaki gibi zamanlamaları 100,000,000 kadar asal sayıları hesaplamak için:

Bit: 3.8 s karakter: 5.8S M-kelimeler: 10.8s

O çirkin bile tüm ilginçtir Sadece bir bit ile bir booleanı temsil etmek için gerekli olan bit kaydırma, genel olarak daha hızlıdır. Benim varsayımım, önbelleğe alma ve konum referansının ekstra ~ 3 komutlarından daha ağır basmasıdır. Artı, n-bit-makine-kelime yönteminin hafızasını 1/nth kullanarak sona eriyorsunuz!

Answer 3

Bana göre, inessential sayıyı hesapladığınız için algoritmanız yavaş çalışıyor. Çok eski yazı var olsa ardından, bu kodu

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

deneyin algoritması "Eratosthenes Sieve" kullanılarak asal sayı oluşturmak için benim denemek değer.

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

} 

Bu birinin yardımcı olacağını umuyorum.

Answer 5

Eratosthenes Sieve algoritmasını kullanan aslında çok basit bir kod. Tüm pozitif int için çalışır.

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