Как проверить является ли число простым c

Функция, проверяющая простое ли число

Необходимо проверить, является ли число простым используя функцию.
Решил вот так, но работает не до конца правильно. Не могу отловить причину.

int prime(unsigned int num < for ( int i = 2; i * i > return 1; > 

Отслеживать
371 1 1 золотой знак 5 5 серебряных знаков 13 13 бронзовых знаков
задан 28 июн 2013 в 17:13
11 1 1 золотой знак 1 1 серебряный знак 2 2 бронзовых знака
«работает не до конца правильно» следует понимать как «не компилируется»?
28 июн 2013 в 17:22

Если добавить пропущенную скобку, проблема будет в возможном переполнении при возведении в квадрат. Знаковое переполнение является undefined behaviour по стандарту.

28 июн 2013 в 17:24

раобтает она у вас правильно, только после unsigned int num вы забыли закрывающую круглую скобку. Ну и еще стоит отметить неоптимальность алгоритма. Но в целом верно

28 июн 2013 в 17:25
@DreamChild: А если num == MAXINT ? Или простое число чуть меньше MAXINT ?
28 июн 2013 в 17:28

@VladD я даже более того скажу — тут достаточно корня из MAXINT плюс один. Хотя, чего уж там — изначально возведение n в квадрат я не заметил.

28 июн 2013 в 17:33

4 ответа 4

Сортировка: Сброс на вариант по умолчанию

bool is_prime(unsigned p) < if ( p < 2 ) return false; if ( p == 2 ) return true; if ( p%2 == 0 ) return false; double limit = sqrt(p); for (unsigned i=3; ireturn true; > 

Отслеживать
ответ дан 30 июн 2013 в 16:43
1,297 12 12 золотых знаков 36 36 серебряных знаков 62 62 бронзовых знака
У Вас маленькая ошибочка — 2-ка это тоже простое число.
30 июн 2013 в 17:57
Да, Вы правы
30 июн 2013 в 21:44

@nullptr, а Вы тестируете, что пишете? — Теперь поменяйте порядок первых if-ов. 2-ка ведь четная и для нее сработает первый if , возвращающий false .

30 июн 2013 в 21:56

Небольшая оптимизация. Сначала проверьте num на равно 2 (простое), меньше 2 и num четное число (не простые). Затем можно перебирать только нечетные:

uint32_t i, lim = sqrt(num) + 1; for (i = 3; i < lim; i += 2) if (num % i == 0) return 0; return 1; 

Глянул асм. код. Несмотря на -O3 чуть лучше так:

 uint32_t i, lim = ((uint32_t)sqrt(num)) + 1; 

@VladD, решето не для этой задачи. Решето - это поиск всех простых (задано их количество). Здесь же требуется проверить только одно число.

Отслеживать
ответ дан 28 июн 2013 в 18:21
46.1k 6 6 золотых знаков 48 48 серебряных знаков 116 116 бронзовых знаков

Вот решение на C++ хотите переписывайте на СИ источник: решето Аткина

#include #include using namespace std; bool is_prime(unsigned int num) < int limit = num; int sqr_lim; vectoris_prime_f(num + 10); int x2, y2; int i, j; int n; // Инициализация решета sqr_lim = (int)sqrt((long double)limit); for (i = 0; i j) && (n > // Отсеиваем кратные квадратам простых чисел в интервале [5, sqrt(limit)]. // (основной этап не может их отсеять) for (i = 5; i > > // Вывод списка простых чисел в консоль. //printf("2, 3, 5"); if ((i == 2) || (i == 3) || (i == 5)) return true; for (i = 6; i > return 0; > int main(int argc, char* argv[]) < if (is_prime(983))< cout else < cout return 0; > 

Отслеживать
371 1 1 золотой знак 5 5 серебряных знаков 13 13 бронзовых знаков
ответ дан 1 июл 2013 в 5:27
10k 16 16 золотых знаков 54 54 серебряных знака 119 119 бронзовых знаков
@perfect, что произойдет если проверить число 4000000001?
1 июл 2013 в 8:12
у меня вывело что число 4000000001 - простое
1 июл 2013 в 10:26

А теперь запускаем проверку на [WolframAlpha][1] и получаем, что 4000000001 = 47 * 127 * 670129, то есть нифига не простое. [1]: wolframalpha.com/input/?i=4000000001

1 июл 2013 в 10:48

@perfect, код @nullptr (естественно поправлен, как в моем комментарии к нему) как раз работает. А вот Ваш код сообщает что число 4000000005 простое, что (даже без вольфрама) очевидно не так. (4000000005 прекрасно делится на 5). Где-то у Вас для чисел больше 2^31 ошибочка закралась.

1 июл 2013 в 11:24

@renegator, так напишите (например в "исследованиях"). @perfect, замените в программе все int на unsigned int . И проверяйте (если дождетесь. ).

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

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

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

Jimmy 08 окт. 2009, в 18:20
Поделиться
Это скорее вопрос математики, чем вопрос программирования?
bdonlan 08 окт. 2009, в 15:46

Вот несколько указателей: int * ptr; int * ptr2; int * ptr3. Извините, ничего не поделаешь Насколько большими будут цифры, которые вы будете проверять? А также, вы хотите эвристику или что-то, что всегда работает?

AlbertoPL 08 окт. 2009, в 15:47

Придумайте свой алгоритм (способ, которым вы тестируете его без кода), и тогда, возможно, мы сможем помочь выразить это в C.

BobbyShaftoe 08 окт. 2009, в 15:49

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

arno 08 окт. 2009, в 15:52
Какой смысл в «i! = Число», когда у вас есть «i <число» в качестве условия для выполнения цикла? Matthieu M. 08 окт. 2009, в 17:36

Взгляните на эту ссылку, она содержит объяснение того, как все работает. cprogramming.language-tutorial.com/2012/01/.

user1236102 03 март 2012, в 17:27

Также обратите внимание, что проверка i < number является излишним. По определению, если число x = a * b , либо a либо b равно < int(sqrt(x)) а другое больше. Таким образом, ваш цикл должен идти только до int(sqrt(x)) .

twalberg 17 май 2013, в 14:28
Показать ещё 5 комментариев
Поделиться:

10 ответов

Лучший ответ

ОК, так что забудьте о 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; ireturn 1; > 

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

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

int IsPrime(int number) < int i; for (i=2; i*ireturn 1; > 

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

int IsPrime(unsigned int number) < if (number return 1; > 

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

Stephen Canon 08 окт. 2009, в 16:21
Поделиться
К вашему сведению, стандарт C99 определяет заголовок , который предоставляет bool , true и false .
Kristopher Johnson 08 окт. 2009, в 16:38
отличный ответ, большое спасибо
Jimmy 08 окт. 2009, в 17:15

также забыл упомянуть, что мне не нужно беспокоиться о 0, 1 или негативах, это просто пробегает список из 50 чисел, если я правильно помню, но еще раз спасибо

Jimmy 08 окт. 2009, в 17:16

@ Кристофер: спасибо, забыл об этом. @Jimmy: рад помочь, рад, что это была только ошибка документации =)

Stephen Canon 08 окт. 2009, в 17:19

Вы также можете улучшить это (почти на 50%), только проверяя нечетные числа (рассматривайте 0,1,2 как особые случаи) и начинайте с 3 заранее по 2 каждый раз.

Tom 08 окт. 2009, в 17:37

Я знаю, что проще вычислить квадрат, чем квадратный корень, однако вычисление квадрата на каждой итерации должно стоить БОЛЬШЕ, чем вычисление квадратного корня один раз, и с этим покончено: x

Matthieu M. 08 окт. 2009, в 17:39

На современной машине с нарушением порядка ожидания задержка команды mul для возведения в квадрат i должна быть полностью скрыта в задержке модуля, поэтому заметного выигрыша в производительности не будет. На машине со строгим порядком можно получить выигрыш при использовании квадратного корня с поднятыми краями, но это может привести к проблемам с неточностью с плавающей запятой, если код был скомпилирован на платформе с большим типом int (64 бита или более) , Все, с чем можно справиться, но я подумал, что лучше держать вещи простыми и тривиально переносимыми. В конце концов, если вы заботитесь о скорости, вы вообще не используете этот алгоритм.

Stephen Canon 08 окт. 2009, в 17:51

@Tom То есть, ты можешь улучшить намного больше, остановившись на полу (sqrt (число)). Возьмите, например, 11, floor (sqrt (11)) = 3. Число после 3 - 4, 3 * 4 = 12> 11. Если вы используете наивное сито для проверки на первичность, вам нужно только проверить нечетное числа до sqrt оригинала, кроме 2.

Calyth 08 окт. 2009, в 23:08

@Matthieu Матье М .: Согласен. Я написал сценарий ruby, чтобы проверить это: 331: Стивен: 0.000635 Матье: 0.000611 68720001023: Стивен: 1.958449 Матье: 0.003167 999999000001: Стивен: 7.293912 Матье: 0.005871

DJTripleThreat 30 май 2010, в 04:39

@Calyth добавление floor () к функции не делает ничего другого, кроме sqrt (), но для выполнения задачи требуется больше времени.

DJTripleThreat 30 май 2010, в 04:58

@StephenCanon: условие завершения цикла for таково: «i
kingsmasher1 27 май 2013, в 04:46
-1. Последняя функция дает неверный ответ для 4294967291 .
davidg 07 апр. 2014, в 03:17
Любил вещь квадратного корня!
gab06 15 окт. 2014, в 20:21

@StephenCanon: и вы также можете заменить этот пост инкремент i++ на ++i . как это также уменьшит один шаг работы.

Abdullah 05 янв. 2015, в 17:40
Z boson 29 апр. 2015, в 08:18

@Zboson: Zboson: Если мы действительно хотим придираться, number/i строго хуже, чем (предварительно вычисленное) sqrt(number) . number/i выполняет одно дополнительное ненужное деление. Это также делает условие цикла зависимым от операции с длительным временем ожидания; в архитектуре с конвейерным делением это может легко привести к задержкам из-за ограничений на количество неразрешенных предсказаний ветвления в полете за один раз.

Stephen Canon 29 апр. 2015, в 10:41

@StephenCanon, вы уже делаете number%i так что вы получаете number/i бесплатно. Это так же быстро, как sqrt(number) . Вы читали мои условные тесты в первичном по пробе делении ?

Z boson 29 апр. 2015, в 12:21

@Zboson: Zboson: это так же быстро на архитектуре без конвейерного разделения , и это не так ясно (на мой взгляд, вкусы могут отличаться).

Stephen Canon 29 апр. 2015, в 13:17

Код, опубликованный OP, был уже на 100% действительным. Таким образом, большая часть этого ответа - просто нонсенс, нет необходимости преобразовывать одну вещь. bool true и false действительно существуют в C. static функции существуют в C, и объявления переменных внутри для циклов допускаются.

Lundin 26 окт. 2015, в 12:56
Вы также можете избавиться от всех четных чисел, поэтому я + = 2
Kasparov92 04 апр. 2016, в 18:45

@Kasparov92 Kasparov92 i начинаю с 2, поэтому i+=2 не правильно. Вы можете попробовать ввести 31 или 33, чтобы проверить это.

CyberMew 30 апр. 2016, в 19:08
@CyberMew позвольте мне начать с 3 и i + = 2, чтобы мы двигались только на нечетных
Kasparov92 01 май 2016, в 10:17

Будучи высоко оцененным ответом, угловые ошибки заслуживают внимания - в коде . 1) IsPrime(0 or 1) неверно сообщает true. 2) Неопределенное поведение с IsPrime(int number) и большим number , 3) IsPrime(unsigned number) : i*i
chux 10 фев. 2019, в 17:56
Показать ещё 21 комментарий

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

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

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

• Этот алгоритм/проблема называется "" Смущающе параллельный"
• Он создает набор простых чисел
• Его пример проблемы динамического программирования
• Быстро!

monksy 10 окт. 2009, в 01:09
Поделиться

Это также O(n) в пространстве, и если ваши вычисления для одного значения, это огромная трата пространства без увеличения производительности.

R.. 29 май 2011, в 21:15
(На самом деле O(n log n) или больше, если вы поддерживаете большие числа . )
R.. 29 май 2011, в 21:16

Кто вычисляет только 1 значение для простого числа в течение срока службы приложения? Простые числа - хороший кандидат для кэширования.

monksy 30 май 2011, в 20:14

Программа командной строки, которая завершается после одного запроса, была бы очевидным примером. В любом случае, сохранение глобального состояния уродливо и всегда должно рассматриваться как компромисс. И я бы сказал, что сито (генерируемое во время выполнения) по сути бесполезно. Если ваши основные кандидаты достаточно малы, чтобы вы могли разместить в памяти сито такого размера, вы должны просто иметь static const растровое изображение static const числа которого просты, и использовать его, а не заполнять его во время выполнения.

R.. 31 май 2011, в 00:01

Или, как правило, запоминание почти всегда бесполезно, если только вы не можете как-то пропустить большие промежутки, так как всякий раз, когда вы можете позволить себе столько памяти, вы могли бы еще легче позволить себе такой большой объем дискового пространства / размер сегмента .text .

R.. 31 май 2011, в 00:03

Сито Эратосфена - хороший (ну, добрый) способ решения проблемы "сгенерировать все простые числа до n ". Это расточительный способ решения проблемы "это п премьер?"

hobbs 10 июнь 2014, в 05:44

Сито Эратосфена является только «смущающей параллелью» для MIMD, а не для SIMD. Современный компьютер использует несколько технологий для распараллеливания, и MIMD - только одна из них. Если вы найдете способ сделать это параллельно для SIMD, пожалуйста, дайте мне знать!

Z boson 29 апр. 2015, в 08:14
Показать ещё 5 комментариев

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

• Алгоритм можно дополнительно улучшить, если заметить, что все простые числа имеют вид 6k ± 1, за исключением 2 и 3.
• Это потому, что все целые числа могут быть выражены как (6k + i) для некоторого целого k и для я = -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 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*ireturn 1; > > 

Blackhat002 05 нояб. 2014, в 15:46
Поделиться
Вы должны вернуть 0 когда (число == 1), так как 1 не простое число.
Ahmad Ibrahim 10 май 2016, в 02:02

Оптимизации такого рода не имеют отношения к ИМО для этой задачи: зачем останавливаться на форме 6k ± 1, кроме 2 и 3 , что повторяется в n ^ 2 mod 6 = 1 , когда вы можете иметь n ^ 4 mod 30 = 1, кроме 2,3 , 5 . на самом деле, вы можете идти вечно, потому что вы используете простые числа для этой оптимизации . и это - самый принцип более общего алгоритма Sieve of Eratosthenes 🙂

ghilesZ 09 апр. 2017, в 10:20

@GhilesZ: я не согласен, это очень актуально для проблемы и с одним "||" позволяет базовому циклу работать эффективно в 3 раза быстрее.

verdy_p 15 авг. 2017, в 21:18

Кроме того, для числа == 1 он корректно возвращает 0 (не простое) с проверенным признанием "(число% 2 == 0)", так как ошибки вообще нет

verdy_p 15 авг. 2017, в 21:20

Метод Eratosthene - это совершенно другой метод, который требует выделения большого массива O (n) логических значений, и он не обязательно будет быстрее из-за индексированных обращений. Этот код хорош, так как он оптимизирует первый случай двух первых простых чисел 2 и 3 (поэтому цикл увеличивается на 2 * 3).

verdy_p 15 авг. 2017, в 21:32

Вы можете продолжить использовать ту же технику, используя следующее простое число (5), с шагом (30 == 2 * 3 * 5) и проверить 9 возможных значений (30k + <1; 7; 11; 13; 17; 19; 21; 23 ; 29>), все еще без использования массива для хрупких Однако я думаю, что быстрее предварительно вычислить sqrt (i), а не вычислять продукт i * i в каждом цикле.

verdy_p 15 авг. 2017, в 21:32

(редактировать: удалить 30k + 21, который делится на 3). Вы видите, что первая оптимизация для двух первых простых чисел выигрывает значительно (в 6 раз меньше циклов, тестирующих 2 кандидата, т.е. в 3 раза быстрее, чем циклов по всем коэффициентам). Оптимизация для первых 3 простых чисел (в 30 раз меньше циклов, тестирующих 8 кандидатов, будет т.е. в 30/8 = 3,75 раза быстрее, чем циклы по всем коэффициентам), но выигрыш менее впечатляющий. Это общее правило: вы не будете значительно быстрее с обычным хрипом!

verdy_p 15 авг. 2017, в 21:42
Показать ещё 5 комментариев

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

Eric Bainville 08 окт. 2009, в 17:11
Поделиться
+1: полное излишество за то, что спрашивал спрашивающий, но, тем не менее, исправить.
Stephen Canon 08 окт. 2009, в 21:54

Обратите внимание, что Гай Л. недавно предложил использовать в ответе и Миллера-Рабина, и он ссылается на rosettacode.org/wiki/Miller-Rabin_primality_test#C - где показана реализация на C с использованием GMP . Запись также имеет ряд реализаций на множестве других языков.

Jonathan Leffler 02 авг. 2015, в 00:09

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

bool check(int n) < if (n 1; > if (n % 2 == 0 || n % 3 == 0) < return false; >int sq=sqrt(n); //include math.h or use i*i > return true; > 

JerryGoyal 30 апр. 2015, в 23:25
Поделиться

Чтобы проверить простое число, вы должны пройти весь путь от i=2 до i
Dr Beco 01 авг. 2015, в 02:40
@DrBeco хорошее наблюдение! спасибо например. обновил код.
JerryGoyal 01 авг. 2015, в 18:49

Тщательно проанализировав проблему ceil() , я понял, что, хотя многие сайты рекомендуют ее, это просто перебор. Вы можете соединиться и проверить только i
Dr Beco 02 авг. 2015, в 06:35
Показать ещё 1 комментарий

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

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

bool IsPrime(int target) < for (i = 2; i > return true; > 

Matt Lacey 08 окт. 2009, в 17:33
Поделиться

Конечно, недостатком является то, что sqrt рассчитывается на каждой итерации, что сильно замедляет его.

Rich Bradshaw 08 окт. 2009, в 16:23

Любой разумный компилятор должен быть в состоянии обнаружить, что корень (цель) является инвариантом цикла и поднять его.

Stephen Canon 08 окт. 2009, в 16:29

(и если у вас есть компилятор, который не может выполнить эту оптимизацию, вы должны обязательно сообщить об ошибке, чтобы автор компилятора знал, что им не хватает этой оптимизации.)

Stephen Canon 08 окт. 2009, в 16:30

наряду со многими другими потенциальными (микро) оптимизациями, если вы вручную получите sqrt перед оператором for, вы также можете проверить его мод (и вернуть false, если 0).

Matt Lacey 09 окт. 2009, в 07:49
Что если целевое значение равно 1?
ffffff01 05 дек. 2012, в 20:10
Показать ещё 3 комментария

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

Запустив обе функции и время проверки, я могу сказать, что эта функция работает быстрее. Давайте посмотрим 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; iqt--; 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 i=0; for(j=0; j return 1; > 

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

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

время начала увеличиваться, с 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 

Как проверить, является ли число простым

Соавтор(ы): Grace Imson, MA. Грейс Имсон — преподаватель математики с более чем 40 годами опыта. В настоящее время преподает математику в Городском колледже Сан-Франциско, ранее работала на кафедре математики в Сент-Луисском университете. Преподавала математику на уровне начальной, средней и старшей школы, а также колледжа. Имеет магистерскую степень по педагогике со специализацией на руководстве и контроле, полученную в Сент-Луисском университете.

Количество источников, использованных в этой статье: 8. Вы найдете их список внизу страницы.

Количество просмотров этой статьи: 213 516.

В этой статье:

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

Часть 1 из 3:

Тесты простоты

Примечание: во всех формулах n обозначает проверяемое число.

Перебор делителей. Достаточно поделить n на все простые числа от 2 до округленного значения( n >> ).

• Выберем целое число a, такое что 2 ≤ a ≤ n - 1.
• Если a n (mod n) = a (mod n), то число, вероятно, простое. Если равенство не выполняется, число n является составным.
• Проверьте данное равенство для нескольких значений a, чтобы увеличить вероятность того, что проверяемое число действительно является простым.

• Найдите величины s и d, такие чтобы n − 1 = 2 s ∗ d *d> .
• Выберите целое число a в интервале 2 ≤ a ≤ n - 1.
• Если a d = +1 (mod n) или -1 (mod n), то n, вероятно, является простым числом. В этом случае перейдите к результату теста. Если равенство не выполняется, перейдите к следующему шагу.
• Возведите ответ в квадрат ( a 2 d > ). Если получится -1 (mod n), то n, вероятно, простое число. В этом случае перейдите к результату теста. Если равенство не выполняется, повторите ( a 4 d > и так далее) до a 2 s − 1 d d>> .
• Если на каком-то шаге после возведения в квадрат числа, отличного от ± 1 (mod n), у вас получилось +1 (mod n), значит n является составным числом. Если a 2 s − 1 d ≠ ± 1 d>\neq \pm 1> (mod n), то n не является простым числом.
• Результат теста: если n прошло тест, повторите его для других значений a, чтобы повысить степень достоверности.

Часть 2 из 3:

Как работают тесты простоты

• Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.

• Во многих калькуляторах есть клавиша mod. В конце данного раздела показано, как вручную вычислять эту функцию для больших чисел.

Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке "чисел Кармайкла" (составных чисел, которые удовлетворяют данному тесту) и "псевдопростых чисел Ферма" (эти числа соответствуют условиям теста лишь при некоторых значениях a). [2] X Источник информации

Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. [3] X Источник информации Составное число не будет принято за простое, если провести расчеты для более ¼ значений a. [4] X Источник информации Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.

• Перепишите выражение в более удобном виде: ( 3 25 ∗ 3 25 ) *3^)> mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
• ( 3 25 ∗ 3 25 ) *3^)> mod 50 = ( 3 25 > mod 50 ∗ 3 25 <\displaystyle *3^> mod 50) mod 50. Здесь мы учли свойство модульного умножения.
• 3 25 <\displaystyle 3^> mod 50 = 43.
• ( 3 25 > mod 50 ∗ 3 25 <\displaystyle *3^> mod 50) mod 50 = ( 43 ∗ 43 ) mod 50.
• = 1849 mod 50.
• = 49 .

Как проверить, является ли число простым в Python?

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

Одним из простых и эффективных способов определения простого числа в Python является использование алгоритма «решето Эратосфена». Этот алгоритм основан на идее удаления всех чисел, кратных проверяемому числу. В результате останутся только простые числа. Это позволяет существенно сократить время проверки простоты числа.

Для реализации алгоритма решета Эратосфена в Python мы можем воспользоваться списком чисел от 2 до заданного числа и последовательно удалять из него все числа, которые являются кратными текущему проверяемому числу. Если в конечном итоге в списке останется только одно число – это значит, что заданное число является простым.

Определение простых чисел в Python

Что такое простые числа?

Простые числа — это натуральные числа, которые имеют ровно два делителя: 1 и само число. Например, числа 2, 3, 5, 7, 11, 13 являются простыми числами.

Алгоритм определения простых чисел

Существуют различные алгоритмы определения простых чисел. Один из самых простых и популярных алгоритмов — это проверка делителей числа. Алгоритм заключается в том, что мы проверяем, делится ли число на все числа от 2 до корня из этого числа. Если число делится хотя бы на одно из этих чисел, то оно является составным, иначе — простым.

В Python можно реализовать этот алгоритм следующим образом:

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

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

Что такое простые числа

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

Простые числа имеют множество уникальных свойств и интересных особенностей. Например, последовательность простых чисел не имеет определенного шаблона и может быть представлена бесконечным множеством. Это было установлено Эратосфеном уже в III веке до н.э.

Смотрите также: ALTER TABLE SQL: синтаксис и применение

Одна из наиболее известных задач, связанных с простыми числами, — это задача о разложении на простые множители. Она заключается в нахождении всех простых чисел, на которые заданное число делится без остатка.

Изучение простых чисел имеет большое значение и привлекает не только математиков, но и ученых из различных областей интересов. Это связано с их уникальными свойствами и возможными применениями. Любой, кто хочет понять мир чисел глубже, не может обойти стороной изучение простых чисел.

Алгоритм проверки числа на простоту

Алгоритм проверки числа на простоту следующий:

1. Проверяем число на делимость на числа от 2 до корня из этого числа.
2. Если число делится на какое-либо из этих чисел без остатка, то оно не является простым.
3. Если в процессе проверки не было найдено делителей, то число является простым.

Этот алгоритм основан на том факте, что если число делится без остатка на какое-то число до его корня, то оно точно имеет делитель больший, чем это число. Поэтому нет смысла проверять делители больше корня из числа, чтобы определить его простоту.

Решето Эратосфена

Алгоритм Решето Эратосфена заключается в следующих шагах:

1. Создаем список чисел от 2 до n, где n — верхняя граница диапазона.
2. Находим самое маленькое число в списке и помечаем его как простое.
3. Удаляем из списка все числа, которые делятся на это простое число.
4. Повторяем шаги 2 и 3, пока не достигнем конца списка.
5. Все оставшиеся числа в списке являются простыми.

Преимущество алгоритма Решето Эратосфена заключается в его эффективности. Время работы алгоритма составляет O(n log log n), что является очень хорошим показателем для нахождения всех простых чисел в заданном диапазоне.

Алгоритм Решето Эратосфена широко используется для решения задач связанных с простыми числами, такими как нахождение суммы простых чисел, нахождение наибольшего простого числа и т.д.

Пример реализации алгоритма Решето Эратосфена на языке Python выглядит следующим образом:

def sieve_of_eratosthenes(n): primes = [True] * (n + 1) primes[0] = primes[1] = False for i in range(2, int(n ** 0.5) + 1): if primes[i]: for j in range(i * i, n + 1, i): primes[j] = False return [i for i, prime in enumerate(primes) if prime]

Этот код возвращает список всех простых чисел до заданного числа n.

Теперь вы знаете, как использовать Решето Эратосфена для определения простых чисел на языке Python. Используйте этот алгоритм для решения задач, связанных с простыми числами, и улучшите производительность своих программ!

Смотрите также: Основы программирования на си

Оптимизация алгоритма

При реализации алгоритма проверки числа на простоту важно учитывать, что существуют оптимизации, которые позволяют сократить время выполнения и улучшить производительность программы. Вот несколько способов оптимизировать алгоритм:

1. Уменьшение количества делителей для проверки. Вместо проверки всех чисел от 2 до n-1, можно ограничиться проверкой делителей только до квадратного корня из числа n. Если число делится на какой-либо делителой больше, чем его квадратный корень, то оно также будет делиться на другой меньший делитель.
2. Использование решета Эратосфена для генерации списка простых чисел. Решето Эратосфена позволяет эффективно находить все простые числа до заданного числа n. Это позволяет ускорить процесс проверки на простоту и использовать предварительно сгенерированный список простых чисел при необходимости.
3. Использование кэширования. Для ускорения повторных проверок чисел на простоту можно использовать кэш, где хранятся уже проверенные числа. Это значительно снизит время выполнения программы в случае повторных проверок одних и тех же чисел.
4. Параллельная обработка. Если необходимо проверить большое количество чисел на простоту, можно использовать параллельную обработку, распределяя задачу между несколькими ядрами процессора. Это позволит снизить время выполнения программы и улучшить производительность.

Оптимизация алгоритма проверки чисел на простоту может быть полезна в случаях, когда необходимо обрабатывать большое количество чисел или когда производительность программы критически важна. Использование этих и других оптимизаций позволит повысить эффективность программы и ускорить выполнение задачи по проверке простоты чисел.

Использование функции для определения простых чисел

Функция для определения простых чисел может быть написана следующим образом:

def is_prime(number): if number  

number = 17 if is_prime(number): print(number, 'является простым числом') else: print(number, 'не является простым числом')