Помогите пожалуйста решить задачу(1 курс)
Простые числа Софи Жермен — это такие простые p, что 2p + 1 тоже простое. Софи Жермен доказала Великую теорему Ферма для показателей, являющихся простыми этого вида. Как и для простых чисел-близнецов, предполагается, что количество таких чисел бесконечно.
Написать программу вывода на экран первых 25 простых чисел Софи Жермен. Числа выводить столбиками, по 5 в строке.
Числа Софи Жермен
Написать программу вывода на экран первых 25 простых чисел Софи Жермен. Числа выводить столбиками, по 5 в строке.
Код:
#include <stdio.h>
#include <conio.h>
void main()
{
int i,j,c,f;
printf("Prostie chisla Sofi Jermen\n");
for(i=1; i<=5; i++)
{
for(j=1; j<=5; j++)
{
/*???*/
printf("%d, ",c);
}
printf("\n");
}
getch();
}
#include <conio.h>
void main()
{
int i,j,c,f;
printf("Prostie chisla Sofi Jermen\n");
for(i=1; i<=5; i++)
{
for(j=1; j<=5; j++)
{
/*???*/
printf("%d, ",c);
}
printf("\n");
}
getch();
}
Код:
#include <stdio.h>
#include <conio.h>
void main()
{
int sofy[]={2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491};
int i,j,c,f;
printf("Prostie chisla Sofi Jermen\n");
for(i=1; i<=5; i++)
{
for(j=1; j<=5; j++)
{
c=sofy[i*5+j];
printf("%d, ",c);
}
printf("\n");
}
getch();
}
#include <conio.h>
void main()
{
int sofy[]={2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491};
int i,j,c,f;
printf("Prostie chisla Sofi Jermen\n");
for(i=1; i<=5; i++)
{
for(j=1; j<=5; j++)
{
c=sofy[i*5+j];
printf("%d, ",c);
}
printf("\n");
}
getch();
}
Наверное, всё-таки, нужно вычислять простые числа, иначе, задание кажется слишком простым и очевидным.
Вот мой код:
За основу взято решето Эратосфена
При помощи него получаем список простых чисел до 400
( оно чуть больше 191*2+1 = 383, максимального числа для сравнения )
После чего выводим только те из них, которые удовлетворяют условию чисел Софи Жермен
Одновременно форматируем:
Вот мой код:
Код:
#include <stdio.h>
#include <conio.h>
#define n 400
void main (void)
{
int m[n];
int p,k,i,j=0;
int d;
int t=0;
int pn=2;
int f;
printf("Prostie chisla Sofi Jermen\n");
for (i=0; i<n; i++) { m[i]=i+pn; }
do {
i=t;
while(1) {
i=i+t+pn;
if (i<n) m[i]=0;
else break;
}
f=1;
while (f && (t<n)) { t++; if (m[t]!=0) f=0; }
j++; m[j]=t+pn;
} while (t<n);
j++;
t=25;
f=5;
d=f;
i=0;
while ((t>0) && (i<j)) {
p=2*m[i]+1;
k=i;
while (k<j) {
k++;
if (m[k]>p) break;
if (m[k]==p) {
printf("%3d, ",m[i]);
d--;
if (d==0) { puts(""); d=f; }
t--;
break;
}
}
i++;
}
getch();
}
#include <conio.h>
#define n 400
void main (void)
{
int m[n];
int p,k,i,j=0;
int d;
int t=0;
int pn=2;
int f;
printf("Prostie chisla Sofi Jermen\n");
for (i=0; i<n; i++) { m[i]=i+pn; }
do {
i=t;
while(1) {
i=i+t+pn;
if (i<n) m[i]=0;
else break;
}
f=1;
while (f && (t<n)) { t++; if (m[t]!=0) f=0; }
j++; m[j]=t+pn;
} while (t<n);
j++;
t=25;
f=5;
d=f;
i=0;
while ((t>0) && (i<j)) {
p=2*m[i]+1;
k=i;
while (k<j) {
k++;
if (m[k]>p) break;
if (m[k]==p) {
printf("%3d, ",m[i]);
d--;
if (d==0) { puts(""); d=f; }
t--;
break;
}
}
i++;
}
getch();
}
При помощи него получаем список простых чисел до 400
( оно чуть больше 191*2+1 = 383, максимального числа для сравнения )
После чего выводим только те из них, которые удовлетворяют условию чисел Софи Жермен
Одновременно форматируем:
На самом деле достаточно написать её имя правильно на английском: Sophie Germain, затем открыть гугл, добавить пару слов. И можно найти интересные вещи, например, что проверка на простоту для этой последовательности может быть реализована много быстрее. Хотя для маленьких чисел особого выигрыша не будет. Этот алгоритм используется в RSA, где для пар ключей реально надо искать большие просты числа.
Кстати, в том же гугле по правильному запросу и с включённым русским языком в настройках где-то 7й ссылкой будет русский блог с кодом на с++, который делает вышеописанное.
Кстати, в том же гугле по правильному запросу и с включённым русским языком в настройках где-то 7й ссылкой будет русский блог с кодом на с++, который делает вышеописанное.