C - определя дали числото е просто

Добре, забравете за C. Да предположим, че ви дам число и ви помоля да определите дали е просто. Как го правиш? Запишете ясно стъпките, след което се погрижете да ги преведете в код.

След като определите алгоритъма, ще бъде много по-лесно за вас да разберете как да напишете програма и за другите да ви помогнат с нея.

редактиране: Ето 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;
}

Това е напълно валидна 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;
}

Това определено не е най-бързият начин да проверите дали числото е просто, но работи и е доста лесно. Едва ли трябваше изобщо да променяме кода ви!

Учудвам се, че никой не спомена това.

Използвайте Ситето на Ератостен

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

1. По принцип непростите числа се делят на друго число освен на 1 и себе си
2. Следователно: непростото число ще бъде произведение на прости числа.

Ситото на Ератостен намира просто число и го запаметява. Когато ново число се проверява за простота, всички предишни прости числа се проверяват спрямо известния списък с прости числа.

Причини:

1. Този алгоритъм/проблем е известен като „Смущаващо паралелен“
2. Той създава колекция от прости числа
3. Това е пример за проблем с динамично програмиране
4. Бързо е!

Стивън Кенън го отговори много добре!

Но

• Алгоритъмът може да бъде подобрен допълнително, като се наблюдава, че всички прости числа са във формата 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; 
      }
  }
  

1. Изградете таблица с малки прости числа и проверете дали те разделят вашето въведено число.
2. Ако числото оцелее до 1, опитайте псевдо тестове за първичност с нарастваща основа. Вижте например тест за първичност на Милър-Рабин.
3. Ако числото ви е оцеляло до 2, можете да заключите, че е просто, ако е под някои добре известни граници. В противен случай вашият отговор ще бъде само "вероятно прост". Ще намерите някои стойности за тези граници в wiki страницата.

тази програма е много ефективна за проверка на едно число за проверка на основността.

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;
}

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

Ако модулът е равен на нула, тогава той не е прост.

псевдо код:

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

  return true;
}

След като прочетох този въпрос, бях заинтригуван от факта, че някои отговори предлагат оптимизация чрез изпълнение на цикъл с кратни на 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) не може да бъде просто число. Това води до друго условие преди 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;
}

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). Умноженията от друга страна са доста евтини.

Избягвайте грешка при препълване

unsigned i, number;
...
for (i=2; i*i<=number; i++) {  // Buggy
for (i=2; i*i<=number; i += 2) {  // Buggy
// or
for (i=5; i*i<=number; i+=6) { // Buggy

Тези форми са неправилни, когато number е просто число и i*i е близо до максималната стойност на типа.

Проблемът съществува при всички цели числа, signed, unsigned и по-широки.

Пример:

Нека UINT_MAX_SQRT като под на корен квадратен от максималната цяло число. напр. 65535, когато unsigned е 32-битов.

При for (i=2; i*i<=number; i++) този 10-годишен неизправност възниква, защото когато UINT_MAX_SQRT*UINT_MAX_SQRT <= number и number е просто число, следващата итерация води до препълване на умножението. Ако типът е подписан тип, препълването е UB. С неподписани типове, това само по себе си не е UB, но логиката се е развалила. Взаимодействията продължават, докато скъсен продукт надвиши number. Може да се получи неправилен резултат. С 32-битов unsigned опитайте 4,294,967,291, което е просто число.

Ако some_integer_type_MAX е било просто число на Мерсен, i*i<=number никога не е вярно.

За да избегнете този бъг, имайте предвид, че 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;
}

Използвайки Ситото на Ератостен, изчислението е доста по-бързо в сравнение с „широкоизвестния“ алгоритъм за прости числа.

Чрез използване на псевдокод от неговото 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.

ЗАБЕЛЕЖКА: Стойността може да варира в зависимост от хардуерните спецификации.