[ create a new paste ] login | about

Link: http://codepad.org/CMneLlht    [ raw code | output | fork ]

C++, pasted on May 3:
#include <iostream>
#include <algorithm>
#include <cmath>
#include <fstream>
 
using namespace std;
 
// big numbers
 
long mulmod(long a, long b, long MOD){
    if (b == 0) return 0;
    long res = mulmod(a, b >> 1, MOD);
    res += res;
    res %= MOD;
    return (b & 1)? (a + res) % MOD : res;
}
 
bool witness(long a, long n) {
    long d = 1;
    long b = n - 1;
    for(int i = 63; i >= 0; i--){
        if(b < pow(2.0, i)) continue;
        long x = d;
        d = mulmod(d, d, n);
        if (d == 1 && x != 1 && x != n - 1) return true;
        if ((b >> i) & 1) d = mulmod(d, a, n);
    }
    return (d != 1);
}
 
bool MillerRabin(long n, long tries) {
    for(int it = 0; it < tries; it++) {
        if(witness(rand() % (n - 1) + 1, n)) 
            return false;
    }
    return true;
}
 
// low numbers
 
#define forn(i, n) for(int i = 0; i < int(n); i++)
 
bool witnessLow(int a, int n) {
    int d = 1;
    int b = n - 1;
    for(int i = 31; i >= 0; i--) {
        if(b < (1 << i)) continue;
        int x = d;
        d = (long(d) * d) % n;
        if(d == 1 && x != 1 && x != n - 1) return true;
        if((b >> i) & 1) d = (long(d) * a) % n;
    }
    return (d != 1);
}
 
bool MillerRabinLow(int n) {
      if(n == 2) return true;
    if(witnessLow(2, n)) return false;
    return true;
}
 
bool test(long c){
    if (c < 1e9)
        return MillerRabinLow(c);
    else 
        return MillerRabin(c, 19);
}
 
int main()
{
		int arr[] = {2047, 3277};
 
	for(int i = 0; i < 2; i++)
	{
		cout<<arr[i]<<" - ";
		if(test(arr[i]))
			cout<<"SIMPLE"<<endl;
		else
			cout<<"NOT SIMPLE"<<endl;
	}
    return 0; 
}


Output:
1
2
2047 - SIMPLE
3277 - SIMPLE


Create a new paste based on this one


Comments: