Показать сообщение отдельно

  #4  
Старый 09.11.2009, 17:22
winflip
Познающий
Регистрация: 13.05.2009
Сообщений: 40
Провел на форуме:
91842

Репутация: 1
По умолчанию

Если не сложно, скажите ещё одну весчь)) Я написал исходник на основе алгоритма, который дан на википедии, называется тест простоты милера-рабина(или миллера-рабина), так вот исходник:
Код:
#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;
}
Проблема в том, что он неработает, смущает концовка, потому что в алгоритме я её не понял.))) Помогите. Простой тест a=3,b=20. Он выводит 15(хотя оно составное), и не выводит 17(оно то как раз простое)
 
Ответить с цитированием