
14.11.2009, 11:50
|
|
Познающий
Регистрация: 13.05.2009
Сообщений: 40
С нами:
8945711
Репутация:
1
|
|
Сообщение от Irdis
не пойдёт вылезает за границы допустимых значений
Переписал, выводит частично не те числа:
Код:
// http://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%9C%D0%B8%D0%BB%D0%BB%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0
#include <cmath>
#include <iostream>
bool is_prime(int);
int main(){
using namespace std;
int a,b;
cin >> a >> b;
for(int i=a;i<=b;i++){
if(is_prime(i)){
cout << i << " ";
}
}
system("PAUSE");
}
bool is_prime(int m){
using namespace std;
int r = 1000;
int t = m-1;
int s = 0;
bool b = true;
if(m==2){
return true;
}
if(m%2==0){
return false;
}
if(m==1){
return false;
}
while(t%2==0 || b){
b = false;
s++;
t=t/2;
}
for(int i=1;i<r+1;i++){
int a = 2+rand()%(m-1);
int x = (long(pow(float(a),float(t))))%m;
if((x==1)||(x==m-1)){
continue;
}
for(int j=1;j<s;j++){
x=(long(pow(float(x),2)))%m;
if(x==1){
return false;
}
if(x==m-1){
break;
}
return false;
}
}
return true;
}
|
|
|