Найти все простые числа Мерсенна, не превышающие 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.