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

Question

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

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

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

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

10 67

javascript c# primes

10 ответов:

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

использовать Решето Эратосфена

детали:

в основном числа нестандартных делиться на другое число, кроме 1 и самих себя

таким образом: непервичное число будет произведением простых чисел.

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

причины:

этот алгоритм / проблема известна как"Параллельной"

он создает коллекцию простых чисел

это пример задачи динамического программирования

быстрая!

26

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

но
алгоритм может быть улучшен далее, наблюдая, что все простые числа имеют вид 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; 
    }
}

13

построить таблицу малых простых чисел, и проверить, если они делят ваш входной номер.

если число сохранилось до 1, Попробуйте псевдо-тесты на примитивность с увеличением базы. Смотрите тест на примитивность Миллера-Рабина например.

Если ваше число сохранилось до 2, Вы можете заключить, что оно простое, если оно ниже некоторых хорошо известных границ. В противном случае ваш ответ будет только "вероятно Прайм". Вы найдете некоторые значения для этих границ на странице Вики.

10

эта программа очень эффективна для проверки одного числа для проверки первичности.
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;
}

4

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

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

псевдо код:
bool IsPrime(int target)
{
  for (i = 2; i <= root(target); i++)
  {
    if ((target mod i) == 0)
    {
      return false;
    }
  }

  return true;
}

3

Я бы просто добавил, что четное число (бар 2) не может быть простым числом. В результате еще до цикла. Поэтому конечный код должен выглядеть так:
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;
}

2

прочитав этот вопрос, я был заинтригован тем, что некоторые ответы предлагали оптимизацию, запустив цикл с кратными 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

2

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 и четных чисел не входит в основной цикл, который обрабатывает только нечетные числа, разделенные нечетными числами. Это связано с тем, что нечетное число по модулю четного числа всегда будет давать ненулевой ответ, что делает эти тесты избыточными. Или, другими словами, нечетное число мая быть равномерно делится на другое нечетное число а никогда на четное число (Е*Е=Е, Е*О=э, О,*Е=>Е и О*О=>О).

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

1

используя сито Эратосфена, вычисление происходит довольно быстро по сравнению с алгоритмом" известных " простых чисел.

С помощью псевдокода из его wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), я могу иметь решение на C#.
public bool IsPrimeNumber(int val) {
    // Using Sieve of Eratosthenes.
    if (val < 2)
    {
        return false;
    }

    // Reserve place for val + 1 and set with true.
    var mark = new bool[val + 1];
    for(var i = 2; i <= val; i++)
    {
        mark[i] = true;
    }

    // Iterate from 2 ... sqrt(val).
    for (var i = 2; i <= Math.Sqrt(val); i++)
    {
        if (mark[i])
        {
            // Cross out every i-th number in the places after i (all the multiples of i).
            for (var j = (i * i); j <= val; j += i)
            {
                mark[j] = false;
            }
        }
    }

    return mark[val];
}
IsPrimeNumber (1000000000) занимает 21s 758ms.

Примечание: значение может варьироваться в зависимости от технических характеристик оборудования.

0

Stephen Canon · Accepted Answer · 2015-12-02 16:57:03

хорошо, так что забудьте о 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 как есть; нет bool введите C, и нет true или false, поэтому вам нужно немного изменить его (edit: Kristopher Johnson правильно указывает, что C99 добавил stdbool.заголовок ч). Поскольку некоторые люди не имеют доступа к среде C99 (но вы должны использовать его!), давайте сделаем это очень незначительное изменение:
int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}
это совершенно действительная программа C, которая делает то, что вы хотите. Мы можем немного улучшить его без особых усилий. Во-первых, обратите внимание, что 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;
}
это определенно не самый быстрый способ проверить, является ли число простым, но это работает, и это довольно просто. Нам даже не пришлось модифицировать ваш код!