By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
I have absolutely no idea how not to brute force this. This is my approach:
function isPrime(n::BigInt)
isPrimeNumber::Bool = true;
if n%2 == 0
isPrimeNumber = false;
return isPrimeNumber
end
for i in 3:2:(n-1)
if n%i == 0
isPrimeNumber = false;
return isPrimeNumber
end
end
return isPrimeNumber
end
function getPrime(primeID::UInt64)
if primeID == 1
prime::BigInt = 2;
else
primeCounter::UInt64 = 2;
prime = 3;
currentNumber::BigInt = 3;
while primeCounter != primeID
currentNumber += 2;
if isPrime(currentNumber)
prime = currentNumber;
primeCounter += 1;
end
end
end
return prime
end
function parseARGS()
if isempty(ARGS)
primeID::UInt64 = 10001;
else
primeID = tryparse(UInt64,ARGS[1]);
end
return primeID
end
function main()
primeID = parseARGS();
prime = getPrime(primeID);
println(prime);
end
main()
$ julia ProjectEuler0007.jl 6
13
0.000064 seconds (215 allocations: 4.430 KiB)
$ julia ProjectEuler0007.jl 60
281
0.001178 seconds (23.06 k allocations: 400.141 KiB)
$ julia ProjectEuler0007.jl 1000
7919
0.573752 seconds (9.37 M allocations: 157.290 MiB, 26.70% gc time)
$ julia ProjectEuler0007.jl 10001
104743
83.428065 seconds (1.24 G allocations: 20.418 GiB, 28.12% gc time)
That is way too slow. I already looked at odd numbers only to save time.