Tests de primalidad

primality-test.cpp

#include <cstdio>
using namespace std;

typedef long long ll;

/**
 * O(n)
 */
bool esPrimoLineal(ll n, ll &contador) {
	contador = 0LL;
	int divisores = 0;
	for(ll i=1; i<=n; i++) {
		contador++;
		if(n % i == 0) divisores++;
	}
	return divisores == 2;
}
/**
 * Optimización salida rápida
 * O(n)
 */
bool esPrimoLinealOp(ll n, ll &contador) {
	contador = 0LL;
	if(n < 2) return false;

	for(ll i=2; i<n; i++) {
		contador++;
		if(n % i == 0) return false;
	}
	return true;
}
/**
 * O(n / 2)
 */
bool esPrimoLinealOp2(ll n, ll &contador) {
	contador = 0LL;
	if(n < 2) return false;
	if(n < 4) return true;
	if(n % 2 == 0) return false;
	for(ll i=3; i<n; i+=2) {
		contador++;
		if(n % i == 0) return false;
	}
	return true;
}
/**
 * O(sqrt(n) / 2)
 */
bool esPrimoRaiz(ll n, ll &contador) {
	contador = 0LL;
	if(n < 2) return false;
	if(n < 4) return true;
	if(n % 2 == 0 || n % 3 == 0) return false;
	for(ll i=5; i*i<=n; i+=2) {
		contador++;
		if(n % i == 0) return false;
	}
	return true;
}
/**
 * Fuente: https://github.com/SuprDewd/CompetitiveProgramming
 * O(sqrt(n) / 3)
 */
bool esPrimoCompetitivo(ll n, ll &contador) {
	contador = 0LL;
	if (n < 2) return false;
	if (n < 4) return true;
	if (n % 2 == 0 || n % 3 == 0) return false;
	if (n < 25) return true;
	for (ll i = 5; i*i <= n; i += 6){
		contador += 2;
		if (n % i == 0 || n % (i + 2) == 0) return false;
	}
	return true;
}

int main() {
	ll contador;
	bool resultado;
	ll primes[10] = {5915587277, 1500450271, 3267000013,
				     5754853343, 4093082899, 9576890767,
					 3628273133, 2860486313, 5463458053,
					 3367900313};

	for(int i=0; i<10; i++) {
		// resultado = esPrimoLineal(primes[i], contador);
		// printf("here\n");
		// printf("1. %lld %d %lld\n", primes[i], resultado, contador);
		// resultado = esPrimoLinealOp(primes[i], contador);
		// printf("2. %lld %d %lld\n", primes[i], resultado, contador);
		// resultado = esPrimoLinealOp2(primes[i], contador);
		// printf("3. %lld %d %lld\n", primes[i], resultado, contador);
		resultado = esPrimoRaiz(primes[i], contador);
		printf("4. %lld %d %lld\n", primes[i], resultado, contador);
		resultado = esPrimoCompetitivo(primes[i], contador);
		printf("5. %lld %d %lld\n", primes[i], resultado, contador);
		printf("***************************************\n");
	}
	return 0;
}