is_prime.cpp

#include <iostream>
using namespace std;

/* this is the most efficient prime number algorithm I could come up with
 * the speed is worst case O(n)
*/
bool isPrime(int n) {
	//two is the only even prime
	if (n == 2) {
		return true;
	}
	//all less than two or divisable by two are not primes
	if (n < 2 || n % 2 == 0) {
		return false;
	}
	//starting from 3, and skipping evens, check up to floor(n/2) is not divisable by i
	int k = n/2;
	for (int i = 3; i < k; i+=2) {
		if (n % i == 0) {
			return false;
		}
	}
	//finally
	return true;
}

int main() {
//	for (int i = 0; i < 1000; i++) {
//		if (isPrime(i)) {
//			cout << i << endl;
//		}
//	}
	int total = 0;
	for (int i = 49979693; i <= 49980841; i++) {
		if (isPrime(i)) {
			total++;
		}
	}
	cout << "Primes found: " << total << endl;
	return 0;
}