Euler Solution 7

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 7

Find the 10001th prime number

C++ by ctd

Runtime: 0.043s

// Half-arsed refactoring of Problem 10
#include <cstdlib>
#include <iostream>
#include <cmath>
#define SEQ_PRIME_NUMBER 10001

using namespace std;

bool isPrime (unsigned int);

int main ()
{
	int primecount = 0;
	unsigned long testNumber = 2;
	while (primecount < SEQ_PRIME_NUMBER) {
		if (isPrime (testNumber)) {
			primecount++;
		}
		testNumber++;
	}

	cout << "Result: " << (testNumber - 1) << endl;

	return EXIT_SUCCESS;
}

bool isPrime (unsigned int i)
{
	if (i <= 1) return false;
	unsigned int upper = sqrt (i) + 1;
	for (unsigned int lower = 2; lower < upper; lower++) {
		if (i % lower == 0)
			return false;
	}
	return true;
}

Haskell by SanguineV

Runtime: 257ms

{- Create a lazy list of prime numbers.
 - Start with 2 and 3 as known primes.
 - After this generate primes using a prime wheel, selecting candidate
 - primes of the form:
 - 6*k + 1 or 6*k + 5
 - Is more efficient by only checking these candidates.
 -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Print the 10000th element of the lazy list = the 10001th prime -}
 main = print (primes !! 10000)

Python by Althalus

Run time: 8.5 Seconds

from math import sqrt
import time

start_time = time.time()
#3 is the second prime. If we start with an odd number, we can go up by 2, as 2 is the only even prime.
number=1
count=1

while count < 10001:
	number+=2 #an even number won't be prime
	prime = True
	i=2
	while i <= sqrt(number)+1:
		if number%i == 0:
			prime=False
			break
		i+=1
	if prime: count+=1 
print (number)
run_time = time.time() - start_time
print (run_time)
Personal tools