Алгоритм простого числа

Question

Может кто-нибудь сказать мне, как реализовать алгоритм Сито Эратосфена в C? Мне нужно сгенерировать простые числа, но мой алгоритм работает медленно.

Мой код:

#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

Вам нужно создать массив булевых значений, равный максимальному простому числу, которое вы хотите найти. В начале он полностью инициализирован как true.

i-я ячейка такого массива будет истинной, если i - простое число, или ложной, если это не так.

Начните итерацию с i=2: это простое число, затем установите значение false в любую ячейку с индексом, кратным 2. Перейти к следующему простому числу (i=3) и сделать то же самое. Перейдите к следующему простому числу (это i=5: i=4 не простое число: array[4] было установлено в false при обработке i=2) и повторите то же самое снова и снова.

Answer 2

На мой взгляд, ваш алгоритм медленный, потому что вы вычисляете несущественное число.попробуйте этот код

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 3

Вот на самом деле очень простой код, который использует алгоритм Sieve of Eratosthenes.работает на все позитивные int.

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

Answer 4

Ссылка Марка Б показывает хороший и простой алгоритм, который является правильным, написанным 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 ...)

Я сравнил три разных способа хранения логических переменных, предложенных peoro. Один метод фактически использует биты, второй занимает целый байт, а последний использует целое машинное слово. Наивным предположением о том, что является самым быстрым, может быть метод машинного слова, так как каждый флаг / логическое значение обрабатывается более «естественно» вашей машиной. Время расчета простых чисел до 100 000 000 на моей машине было следующим:

Биты: 3.8с Символы: 5.8с М-слова: 10,8 с

Интересно отметить, что даже все уродливые сдвиги битов, необходимые для представления логического значения только с одним битом, все еще быстрее в целом. Моя гипотеза состоит в том, что кэширование и локальность ссылок, кажется, перевешивают дополнительные ~ 3 инструкции. Кроме того, вы в конечном итоге используете 1 / nth памяти метода n-битного машинного слова!

Answer 5

Хотя это очень старая статья, я попытаюсь сгенерировать простое число, используя «Сито Эратосфена» .

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

}

Надеюсь, это кому-нибудь поможет.