| |
|
|
| | Скажите пожалуйста, где можно найти исходный код, написанный на c++, для решения задачи на простоту числа с помощью алгоритма Миллера-Рабина | |
| |
|
|
| |
|
|
| |
для: winflip
(26.10.2009 в 17:52)
| | | http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
здесь псевдокод. перевести не сложно | |
| |
|
|
| |
|
|
| |
для: AlMag
(02.11.2009 в 11:35)
| | | Я написал код, но он не корректно работает(почему-то). Проверьте плз
#include <iostream>
#include <cmath>
int is_prime(int m){
using namespace std;
int r = 1000;
int t = m-1;
int s = 0;
bool b = true;
if(m%2==0){
return false;
}
if(m==1){
return false;
}
if(m==2){
return true;
}
while(t%2==0 || b){
b = false;
s++;
t=t/2;
}
for(int i=1;i<r+1;i++){
int a = 2+rand()%(m-2);
int x = int(float(pow(float(a),float(t))))%m;
if((x==1)||(x==m-1)){
continue;
}
for(int j=1;j<s;j++){
x=int(float(pow(float(x),2)))%m;
if(x==1){
return false;
}
if(x==m-1){
continue;
}
}
}
return true;
}
int main(){
using namespace std;
int a,b;
cin >> a >> b;
for(int i=a;i<b;i++){
if(is_prime(i)){
cout << i << " ";
}
}
cin >> a;
return 0;
} |
PS. Что то не пойму скопировал, отступы были, а сейчас нету, нажал править сообщение опять есть, а вт еме нету | |
| |
|
|
