Найти все простые числа Мерсенна, не превышающие 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
.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д