Skip to content

Instantly share code, notes, and snippets.

@Ratstail91
Last active January 31, 2024 09:00
Show Gist options
  • Save Ratstail91/5749374 to your computer and use it in GitHub Desktop.
Save Ratstail91/5749374 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment