C - определить, является ли число простым

Question

Я пытаюсь найти метод, который принимает целое число и возвращает логическое значение, чтобы сказать, является ли число простым или нет, и я не знаю много C; кто-нибудь захочет дать мне несколько советов?

В принципе, я бы сделал это на C # так:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0 && i != number)
            return false;
    }
    return true;
}

Answer 1

ОК, так что забудьте о C. Предположим, я дам вам номер и попрошу вас определить, простое ли это число. Как ты делаешь это? Четко запишите шаги: , а затем беспокойтесь о переводе их в код.

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

edit: Вот код C #, который вы разместили:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

Это очень почти действительный C как есть; в C нет типа bool и true или false, поэтому вам нужно немного его изменить (правка: Кристофер Джонсон правильно указывает, что C99 добавил заголовок stdbool.h). Поскольку некоторые люди не имеют доступа к среде C99 (но вы должны ее использовать!), Давайте внесем это очень незначительное изменение:

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

Это совершенно допустимая программа на Си, которая делает то, что вы хотите. Мы можем немного улучшить его без особых усилий. Во-первых, обратите внимание, что i всегда меньше number, поэтому проверка, что i != number всегда успешна; мы можем избавиться от этого.

Кроме того, вам на самом деле не нужно пробовать делители вплоть до number - 1; Вы можете прекратить проверку, когда вы достигнете sqrt (число). Поскольку sqrt - это операция с плавающей запятой, которая приносит целую кучу тонкостей, мы на самом деле не будем вычислять sqrt(number). Вместо этого мы можем просто проверить, что i*i <= number:

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

Еще одна вещь, хотя; была небольшая ошибка в вашем оригинальном алгоритме! Если number отрицательно, или ноль, или единица, эта функция будет утверждать, что число простое. Скорее всего, вы захотите обработать это должным образом и, возможно, захотите, чтобы number был без знака, так как вы, скорее всего, заботитесь только о положительных значениях:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

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

Answer 2

Я удивлен, что никто не упомянул это.

Используйте Сито Эратосфена

Подробности:

1. В основном непростые числа делятся на другое число, кроме 1 и самих себя
2. Следовательно: непростое число будет произведением простых чисел.

Сито Эратосфена находит простое число и сохраняет его. Когда новый номер проверяется на простоту, все предыдущие простые числа сравниваются с известным списком простых чисел.

Причины:

1. Этот алгоритм / проблема известна как " Параллельно смущающая "
2. Создает коллекцию простых чисел
3. Это пример задачи динамического программирования
4. Это быстро!

Answer 3

Стивен Кэнон ответил очень хорошо!

Но

• Алгоритм может быть улучшен, если наблюдать, что все простые числа имеют форму 6k ± 1, за исключением 2 и 3.
• Это потому, что все целые числа могут быть выражены как (6k + i) для некоторого целого числа k и для i = -1, 0, 1, 2, 3 или 4; 2 делит (6k + 0), (6k + 2), (6k + 4); и 3 делит (6k + 3).
• Таким образом, более эффективный метод - проверить, делится ли n на 2 или 3, а затем проверить все числа в форме 6k ± 1 ≤ √n.

• Это в 3 раза быстрее, чем тестирование всех m до √n.

  int IsPrime(unsigned int number) {
      if (number <= 3 && number > 1) 
          return 1;            // as 2 and 3 are prime
      else if (number%2==0 || number%3==0) 
          return 0;     // check if number is divisible by 2 or 3
      else {
          unsigned int i;
          for (i=5; i*i<=number; i+=6) {
              if (number % i == 0 || number%(i + 2) == 0) 
                  return 0;
          }
          return 1; 
      }
  }
  

Answer 4

1. Составьте таблицу из небольших простых чисел и проверьте, делят ли они ваш входной номер.
2. Если число сохранилось до 1, попробуйте тесты псевдопримальности с возрастающей базой. См., Например, тест первичности Миллера-Рабина .
3. Если ваше число дожило до 2, вы можете заключить, что оно простое, если оно ниже некоторых известных границ. В противном случае ваш ответ будет только «вероятно, простым». Некоторые значения этих границ вы найдете на вики-странице.

Answer 5

эта программа очень эффективна для проверки единственного числа для проверки простоты.

bool check(int n){
    if (n <= 3) {
        return n > 1;
    }

    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
        int sq=sqrt(n); //include math.h or use i*i<n in for loop
    for (int i = 5; i<=sq; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

Answer 6

Прочитав этот вопрос, я был заинтригован тем фактом, что некоторые ответы предлагали оптимизацию, выполняя цикл с коэффициентами, кратными 2 * 3 = 6.

Итак, я создаю новую функцию с той же идеей, но с кратными 2 * 3 * 5 = 30.

int check235(unsigned long n)
{
    unsigned long sq, i;

    if(n<=3||n==5)
        return n>1;

    if(n%2==0 || n%3==0 || n%5==0)
        return 0;

    if(n<=30)
        return checkprime(n); /* use another simplified function */

    sq=ceil(sqrt(n));
    for(i=7; i<=sq; i+=30)
        if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0 
           || n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0)
            return 0;

        return 1;
}

Запустив обе функции и проверив время, я могу утверждать, что эта функция действительно быстрее. Давайте посмотрим на 2 теста с 2 различными простыми числами:

$ time ./testprimebool.x 18446744069414584321 0
f(2,3)
Yes, its prime.    
real    0m14.090s
user    0m14.096s
sys     0m0.000s

$ time ./testprimebool.x 18446744069414584321 1
f(2,3,5)
Yes, its prime.    
real    0m9.961s
user    0m9.964s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 0
f(2,3)
Yes, its prime.    
real    0m13.990s
user    0m13.996s
sys     0m0.004s

$ time ./testprimebool.x 18446744065119617029 1
f(2,3,5)
Yes, its prime.    
real    0m10.077s
user    0m10.068s
sys     0m0.004s

Так что я подумал, получит ли кто-то слишком много, если его обобщить? Я придумал функцию, которая сначала сделает осаду для очистки заданного списка простых чисел, а затем использует этот список для вычисления большего.

int checkn(unsigned long n, unsigned long *p, unsigned long t)
{
    unsigned long sq, i, j, qt=1, rt=0;
    unsigned long *q, *r;

    if(n<2)
        return 0;

    for(i=0; i<t; i++)
    {
        if(n%p[i]==0)
            return 0;
        qt*=p[i];
    }
    qt--;

    if(n<=qt)
        return checkprime(n); /* use another simplified function */

    if((q=calloc(qt, sizeof(unsigned long)))==NULL)
    {
        perror("q=calloc()");
        exit(1);
    }
    for(i=0; i<t; i++)
        for(j=p[i]-2; j<qt; j+=p[i])
            q[j]=1;

    for(j=0; j<qt; j++)
        if(q[j])
            rt++;

    rt=qt-rt;
    if((r=malloc(sizeof(unsigned long)*rt))==NULL)
    {
        perror("r=malloc()");
        exit(1);
    }
    i=0;
    for(j=0; j<qt; j++)
        if(!q[j])
            r[i++]=j+1;

    free(q);

    sq=ceil(sqrt(n));
    for(i=1; i<=sq; i+=qt+1)
    {
        if(i!=1 && n%i==0)
            return 0;
        for(j=0; j<rt; j++)
            if(n%(i+r[j])==0)
                return 0;
    }
    return 1;
}

Полагаю, я не оптимизировал код, но это справедливо. Теперь тесты. Из-за большого количества динамической памяти я ожидал, что список 2 3 5 будет немного медленнее, чем жестко запрограммированный список 2 3 5. Но это было хорошо, как вы можете видеть ниже. После этого время становилось все меньше и меньше, кульминацией которого стал лучший список:

2 3 5 7 11 13 17 19

с 8,6 секундами. Поэтому, если кто-то создаст жестко запрограммированную программу, которая использует такую ​​технику, я бы предложил использовать список 2, 3 и 5, потому что выигрыш не такой большой. Но также, если вы хотите, чтобы код, этот список в порядке. Проблема в том, что вы не можете указать все случаи без цикла, иначе ваш код будет очень большим (1658879 ORs, то есть || в соответствующем внутреннем if). Следующий список:

2 3 5 7 11 13 17 19 23

время начало увеличиваться с 13 секунд. Здесь весь тест:

$ time ./testprimebool.x 18446744065119617029 2 3 5
f(2,3,5)
Yes, its prime.
real    0m12.668s
user    0m12.680s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7
f(2,3,5,7)
Yes, its prime.
real    0m10.889s
user    0m10.900s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11
f(2,3,5,7,11)
Yes, its prime.
real    0m10.021s
user    0m10.028s
sys     0m0.000s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13
f(2,3,5,7,11,13)
Yes, its prime.
real    0m9.351s
user    0m9.356s
sys     0m0.004s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17
f(2,3,5,7,11,13,17)
Yes, its prime.
real    0m8.802s
user    0m8.800s
sys     0m0.008s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19
f(2,3,5,7,11,13,17,19)
Yes, its prime.
real    0m8.614s
user    0m8.564s
sys     0m0.052s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23
f(2,3,5,7,11,13,17,19,23)
Yes, its prime.
real    0m13.013s
user    0m12.520s
sys     0m0.504s

$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29
f(2,3,5,7,11,13,17,19,23,29)                                                                                                                         
q=calloc(): Cannot allocate memory

---

PS. Я не освободил (r) намеренно, предоставив эту задачу ОС, так как память будет освобождена, как только программа выйдет, чтобы получить некоторое время. Но было бы разумно освободить его, если вы намерены продолжать выполнение кода после расчета.

---

БОНУС

int check2357(unsigned long n)
{
    unsigned long sq, i;

    if(n<=3||n==5||n==7)
        return n>1;

    if(n%2==0 || n%3==0 || n%5==0 || n%7==0)
        return 0;

    if(n<=210)
        return checkprime(n); /* use another simplified function */

    sq=ceil(sqrt(n));
    for(i=11; i<=sq; i+=210)
    {    
        if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 || 
   n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 || 
   n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 || 
   n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 || 
   n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 || 
   n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 || 
   n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 || 
   n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 || 
   n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 || 
   n%(i+188)==0 || n%(i+198)==0)
            return 0;
    }
    return 1;
}

Время:

$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real    0m9.123s
user    0m9.132s
sys     0m0.000s

Answer 7

Проверьте модуль каждого целого числа от 2 до корня проверяемого числа.

Если модуль равен нулю, то он не прост.

псевдокод:

bool IsPrime(int target)
{
  for (i = 2; i <= root(target); i++)
  {
    if ((target mod i) == 0)
    {
      return false;
    }
  }

  return true;
}

Answer 8

Я бы просто добавил, что ни одно четное число (столбец 2) не может быть простым числом. Это приводит к другому условию до цикла for. Таким образом, код конца должен выглядеть следующим образом:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

Answer 9

int is_prime(int val)
{
   int div,square;

   if (val==2) return TRUE;    /* 2 is prime */
   if ((val&1)==0) return FALSE;    /* any other even number is not */

   div=3;
   square=9;    /* 3*3 */
   while (square<val)
   {
     if (val % div == 0) return FALSE;    /* evenly divisible */
     div+=2;
     square=div*div;
   }
   if (square==val) return FALSE;
   return TRUE;
}

Обработка 2 и четных чисел не допускается в основной цикл, который обрабатывает только нечетные числа, разделенные на нечетные числа. Это потому, что нечетное число по модулю четное число всегда будет давать ненулевой ответ, что делает эти тесты избыточными. Или, другими словами, нечетное число может быть равномерно делимым на другое нечетное число, но никогда не на четное число (E * E => E, E * O => E, O * E => E и O * O => O).

Деление / модуль действительно дорогостоящий в архитектуре x86, хотя как дорого варьируется (см. http://gmplib.org/~tege/x86-timing.pdf). С другой стороны, умножения довольно дешевы.

Answer 10

Используйте for (i = 2; i <= number/i; i++) для ограничения итераций.

number%i, number/i эффективен на многих компиляторах, так как вычисления отношения и остатка выполняются вместе, что не требует дополнительных затрат для выполнения обоих задач, против всего 1.

Очень простое решение:

bool IsPrime(unsigned number) {
    for(unsigned i = 2; i <= number/i; i++){
        if(number % i == 0){
            return false;
        }
    }
    return number >= 2;
}