Здравствуйте muh, Вы писали:
muh>Здравствуйте vladsm, Вы писали:
V>>I) Тест Леманна
V>>II) Очень распространенный тест Рабина-Миллера
muh>+ еще вариант с построением дерева Кэли %)
Кстати кому интересно я тут еще один способ нарыл
#include <stdio.h>
#include <conio.h>
#include <math.h>
unsigned long n; /* нечетное число, проверяемое на простоту */
/* SPP - функция, равная 1, если */
/* n - сильно псевдопростое число по основанию b */
/* и 0, в противном случае */
int SPP(int b) {
register int k,i;
static unsigned long q;
/* p и x - переменные для точного (64 двоичных разряда) */
/* выполнения промежуточных умножений по mod n */
static double long p,x;
/* вычисление k и нечетного q таких, что n-1=q*2^k */
for(q=n-1,k=0;q%2==0;q>>=1,k++);
/* вычисление p=mod(b^q,n); */
for(x=b,p=q%2?x:1,q>>=1;q>0;q>>=1) {
x=fmodl(x*x,n);
if(q%2) p=fmodl(p*x,n);
}
if(p==1||p==n-1) return 1;
/* поиск i, для которого mod(q*2^i.n)=n-1 */
for(i=1;i<k;i++) if((p=fmodl(p*p,n))==n-1) return 1;
return 0;
}
/*--------------------------------------------------------------------------*/
int main(void) {
FILE *out;
static char *name="rez1.txt"; /* имя файла с результатом */
static unsigned long B,E; /* вводимый диапазон поиска */
static unsigned long NB,NE; /* приведенный диапазон поиска */
static unsigned long k; /* количество простых чисел */
static short p[4]={2,3,5,7},i; /* первые четыре простых числа */
clrscr();
printf("Команда 054. Задача 1.\n");
printf("Простые числа в диапазоне от NB до NE\n");
printf("1<=NB<=NE<=4294967295\n");
/* ввод и приведение начала диапазона к нечетному числу */
printf("NB="); scanf("%lu",&B);
if(B<1) {fprintf(stderr,"*** ошибка NB=%lu\n",B); return 1;}
NB=B; if(B%2==0) NB++;
/* ввод и приведение конца диапазона к нечетному числу */
printf("NE="); scanf("%lu",&E);
if(E<B) {fprintf(stderr,"*** ошибка NE=%lu\n",E); return 1;}
NE=E; if(E%2==0) NE--;
out=fopen(name, "wt");
/* проверка принадлежности введенному диапазону */
/* первых четырех простых чисел */
for(k=0,i=0;i<4;i++) if((B<=p[i])&&(p[i]<=E)) {
k++; fprintf(out," %u",p[i]);
}
/* поиск оставшихся простых чисел в приведенном диапазоне */
n=7; if(NB>9) n=NB-2;
while(n<NE) {
n+=2;
if(SPP(2)&&SPP(3)&&SPP(5)&&SPP(7)&&n!=3215031751L) {
k++; fprintf(out," %lu",n);
}
}
fclose(out);
printf("Количество простых чисел = %lu\n",k);
printf("Результат работы программы записаны в файл %s\n",name);
return 0;
}
Взято отсюда
http://www.tl.ru/~gimn13/docs/dooi/054/054ZDCH1.html
