Я пытаюсь найти метод, который принимает целое число и возвращает логическое значение, чтобы сказать, является ли число простым или нет, и я не знаю много C; кто-нибудь хотел бы дать мне несколько указателей?
В принципе, я бы сделал это на С# следующим образом:
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
ОК, так что забудьте о C. Предположим, я даю вам номер и попрошу вас определить, будет ли он просто. Как ты делаешь это? Запишите шаги четко, а затем подумайте о переводе их в код.
После определения алгоритма вам будет намного легче понять, как писать программу, а другим - помочь вам с ней.
edit: Здесь вы отправили код С#:
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, а no 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;
}
Это определенно не самый быстрый способ проверить, является ли число простым, но оно работает, и это довольно просто. Нам почти не пришлось изменять код вообще!
Я удивлен, что никто не упомянул об этом.
Используйте Сито Эратосфена
Подробности:
Сито Эратосфена находит простое число и хранит его. Когда новый номер проверяется на предмет грубости, все предыдущие простые числа проверяются на знаковый основной список.
Причины:
Стивен Канон ответил на это очень хорошо!
Но
Это в 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;
}
}
Проверить модуль каждого целого числа от 2 до корня числа, которое вы проверяете.
Если модуль равен нулю, то он не является простым.
псевдокод:
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
эта программа очень эффективна для проверки единственного числа для проверки правильности.
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;
}
Я бы просто добавил, что четное число (bar 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 * 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 теста с двумя разными штрихами:
$ 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) не освобождал эту задачу ОС, так как память была бы освобождена, как только программа вышла, чтобы получить некоторое время. Но было бы разумно освободить его, если вы намереваетесь продолжать выполнять свой код после расчета.
BONUS
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
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 = > О).
Разделение/модуль на самом деле дорого стоит на архитектуре x86, но насколько это дорого (см. http://gmplib.org/~tege/x86-timing.pdf). Умножения с другой стороны довольно дешевы.
Используя Сито Эратосфена, вычисление происходит довольно быстро по сравнению с алгоритмом простых чисел "общеизвестный".
Используя псевдокод из него wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), я смогу получить решение на С#.
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) занимает 21 с 758 мс.
ПРИМЕЧАНИЕ. Значение может зависеть от технических характеристик оборудования.