Skip to content

Instantly share code, notes, and snippets.

@aweis
Created January 29, 2014 07:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save aweis/8683471 to your computer and use it in GitHub Desktop.
Save aweis/8683471 to your computer and use it in GitHub Desktop.
Find all Mersenne Primes in C given enough memory and time
#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <stdlib.h>
int
isPrime(uintmax_t n) {
if (n < 2) {
return 0;
} else if (n == 2 || n == 3) {
return 1;
} else if (n % 2 == 0 || n % 3 == 0) {
return 0;
} else {
double max_divisor = sqrt(n);
int divisor = 5;
while (divisor <= max_divisor) {
if (n % divisor == 0 || n % (divisor + 2) == 0) {
return 0;
}
divisor += 6;
}
return 1;
}
}
int
isMersennePrime(uintmax_t n) {
return (isPrime(n) && (fmod(log2(n+1), 1) == 0.0));
}
int main(int argc, char** argv) {
uintmax_t num = 1;
while (1) {
if(isMersennePrime(num)) {
printf("%lu is a mersenne prime\n", num);
}
num+=2; // only odd numbers can be mersenne primes
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment