Найти все простые числа Мерсенна, не превышающие n - C (СИ)
Формулировка задачи:
#include <iostream> #include <math.h> #pragma warning(disable : 4996) using namespace std; int prv(int n) { register int d; for (d=2; d<=n/2; d++) if (n%d==0) return 0; return 1; } int main() { int n,ok; printf("Vvedite n:\n"); scanf("%d",&n); ok=0; for (int i=2;n;i++) if (prv(i) && pow(2,i)<n) if (prv(pow(2,i)-1)) { printf("%d\n",pow(2,i)-1,"=2^\n","%d\n",&i,"-1 \n"); ok++; } return 0; }
Решение задачи: «Найти все простые числа Мерсенна, не превышающие n»
#include <stdio.h> #include <math.h> bool Probe(int nn) { for (int ii = 2; ii <= (nn / 2); ++ii) { if (!(nn % ii)) { return false; } } return true; } int main(int argc,char** argv) { int nn = 0; printf("Enter N: "); scanf("%d",&nn); for (int ii = 2; ii < nn; ++ii) { int pp = (int)pow(2,ii); if (Probe(ii)) { if (Probe(pp - 1)) { printf("pow(2,%d) - 1 = %d\n",ii,pp - 1); } } } return 0; }
Объяснение кода листинга программы
В этом коде реализована функция Probe
, которая проверяет, является ли число nn
простым числом Мерсенна. Простое число Мерсенна - это число вида 2^p - 1, где p - простое число.
В функции main
пользователю предлагается ввести число nn
, которое будет использоваться для поиска простых чисел Мерсенна. Затем происходит итерация по всем числам от 2 до nn - 1
. Для каждого числа ii
вычисляется его простое число Мерсенна pp
как pow(2,ii)
. Затем вызывается функция Probe
для проверки, является ли pp
простым числом. Если это так, то проверяется, является ли (pp - 1)
также простым числом. Если оба числа являются простыми, то выводится значение pp - 1
.
Обратите внимание, что этот код не оптимизирован для больших значений nn
. Для больших значений nn
время выполнения может быть очень долгим из-за того, что проверка на простоту числа выполняется для каждого числа в диапазоне от 2 до nn / 2
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д