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

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

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;

}

Вот на самом деле очень простой код, использующий алгоритм сита Эратосфена. работает на все положительные int.

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

показывает красивый и простой алгоритм, написанный 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+1,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+1,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+1,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);
    }
    printf("Run time: %f\n", t); //print time to find primes

    return 0;
}

Поскольку здесь используется sqrt, для компиляции используйте: gcc prime.c -lm

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

Биты: 3,8 с. Символы: 5,8 с. M-слов: 10,8 с.

Интересно отметить, что даже все уродливые битовые сдвиги, необходимые для представления логического значения с одним битом, в целом все равно быстрее. Я предполагаю, что кеширование и локальность ссылки перевешивают лишние ~ 3 инструкции. Кроме того, вы в конечном итоге используете 1 / n-ю памяти метода 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]);
    }
  }

}

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

Первый шаг - понять, что разбить его на блоки произвольного размера - тривиально; и что вам НЕ нужен массив (или битовое поле) для каждого числа. Например, если вас интересуют только числа от 100000 до 110000, то для того, чтобы пометить все числа, которые делятся на 3, как «непростые», вы можете сделать «for( index = 3 * (100000+3-1)/3; index < 110000; index += 3) {». Для более гибкого примера:

    for( value = 2; value < sqrt( block_end_value-1); value++ ) {
        for( index = value  * (block_state_value+value -1)/value; index < block_end_value; index += value ) {
            mark_not_prime(index - block_state_value);
        }
    }

Второй шаг - понять, что вам не нужно заботиться о каждом числе (а указанное выше for( value = 2; value < sqrt( block_end_value-1); value++) неэффективно). Например, если вы уже отметили числа, которые делятся на 2, как «непростые», то нет причин беспокоиться о том, делятся ли числа на 4, 6 или 8; и если вы уже отметили числа, которые делятся на 3, как «непростые», то нет причин беспокоиться о том, делятся ли числа на 6, 9 или 12; и ... По сути, вы хотите только проверить, делится ли число на другое простое число. Это означает, что для поиска простых чисел в диапазоне от 100000 до 110000 вы сначала хотите найти простые числа в диапазоне от 0 до sqrt (110000); и если вы хотите найти простые числа в диапазоне от 0 до sqrt (110000), вы хотите найти простые числа в диапазоне от 0 до sqrt (sqrt (110000)); и ....

Третий шаг - понять, что его можно ускорить, копируя повторяющиеся узоры. Вы можете создать 2-битный шаблон (представляющий «делится на 2») и везде копировать эти 2 бита. Таким же образом вы можете создать 6-битный шаблон (представляющий «делится на 2 или 3») и везде копировать эти 6 бит. Таким же образом вы можете создать 39916800-битный шаблон (представляющий "делится на 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11") и скопировать этот 39916800-битный шаблон повсюду. Конечно, ничто не мешает вам предварительно сгенерировать шаблон и сохранить его в коде вашей программы.

Четвертый шаг - понять, что числа, кратные 2, слишком тривиальны для хранения, и, не сохраняя их, вы вдвое уменьшаете потребление памяти всеми таблицами и шаблонами (и любым сохраненным / предварительно сгенерированным шаблоном).

Объединив третий и четвертый шаги, указанные выше; предварительно сгенерированный шаблон, представляющий «делится на 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11», будет стоить 19958400 бит, или около 2,38 МБ. Сама по себе первая часть этого шаблона также может быть использована для поиска простых чисел от 1 до первого простого числа, которое больше 11 (в данном случае это будут числа от 1 до 13).

Пятый шаг - понять, что если у вас уже есть шаблон, вы можете использовать его, чтобы найти "N = the next "not marked yet" prime number", скопировать существующий шаблон N раз, а затем пометить числа, кратные N, как "непростые"; и в итоге получится более крупный узор. Например; если у вас есть шаблон, представляющий "делится на 2, 3, 4, 5, 6, 7, 8, 9, 10 и 11", вы пропустите 12 (потому что он не является простым в соответствии с существующим шаблоном); скопируйте образец 13 раз, затем пометьте числа, которые делятся на 13, как «не простые» и получите образец, представляющий «делится на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11». , 12 и 13 ".

Шестой шаг - осознать, что как только у вас есть шаблон, достаточно большой для нужного вам диапазона, вы можете заполнить недостающие делители без копирования. Например, если вам нужны только простые числа в диапазоне от 1 до 6227020800; затем вы можете взять образец, представляющий "делится на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 и 13", а затем отметить числа, которые делятся на простые числа в диапазоне от 14 до 6227020800 как «непростое».

Объединив все вышеперечисленное; если вы хотите найти простые числа в диапазоне от 1000000000 до 11000000000; тогда вы должны начать с поиска простых чисел в диапазоне от 1 до sqrt (11000000000); и для этого вы должны скопировать предварительно сгенерированный шаблон и расширить его до тех пор, пока у вас не будет таблицы, достаточно большой для представления простых чисел в диапазоне от 1 до sqrt (11000000000); затем скопируйте этот расширенный шаблон и заполните отсутствующие числа, чтобы сгенерировать таблицу, представляющую простые числа в диапазоне от 1 до sqrt (11000000000); затем создайте таблицу простых чисел в диапазоне от 1000000000 до 11000000000 и инициализируйте память, скопировав в нее данные из «расширенного предварительно сгенерированного шаблона», затем используйте таблицу простых чисел в диапазоне от 1 до sqrt (11000000000), чтобы найти простые числа, которые еще не были включены в «расширенный предварительно сгенерированный шаблон», чтобы найти числа, которые все еще нужно пометить как «непростые», которые вам понадобятся для создания таблицы для чисел от 1000000000 до 11000000000.

Ответ Тоомтарма Кунга отличный, большое спасибо.

Однако есть еще одно предостережение, на которое я наткнулся: (i*i) может переполняться для i>46340 на 32-битной и i>3037000499 на 64-битной, что дает неверные результаты, т.е. 2147483647 не будет распознан как простое число при использовании 32-битных целых чисел.

Чтобы избежать целочисленного переполнения, можно заменить (i * i)<=number на i <= number / i

Теперь, чтобы избежать двойного деления, код можно записать следующим образом:

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