function isprime(n)
for i = 1:Int(floor(sqrt(n)))
if n % i == 0
return false
end
end
return true
end
@time isprime(10000001829379821798314198278324234)
0.025277 seconds (62.29 k allocations: 2.892 MiB)
Python:
import math, time
def isprime(n):
for i in range(1,int(math.sqrt(n))):
if n%i == 0:
return False
return True
start = time.process_time()
print(isprime(10000001829379821798314198278324234))
end = time.process_time() - start
print(end)
False
1.6626999999998227e-05
Edit: @btime gives 24 ns which is faster than python, I guess @time is something totally different.
julia> function isprime(n)
for i = 2:Int(floor(sqrt(n)))
if n % i == 0;
return false
end
end
return true
end
isprime (generic function with 1 method)
julia> using BenchmarkTools
julia> @btime isprime(999331)
4.386 μs (0 allocations: 0 bytes)
true
The square root is not outside the range of Int64, but with larger inputs you can get into trouble.
And secondly: Int(floor(sqrt(n))), gives you the wrong number:
julia> n = 10000001829379821798314198278324234
10000001829379821798314198278324234
julia> Int(floor(sqrt(n))) # you should rather use floor(Int, sqrt(n)), actually
100000009146898688
julia> isqrt(n) # this is the largest integer m such that m^2 < n
100000009146898690
Also, your example input is an even number, so it will exit on the first division test, so it’s not a good test number. And, if you actually choose a prime number that big, your algorithm would take incredibly long to return.
Compare this with the function from the Primes package:
julia> using Primes
julia> p = nextprime(10^18)
1000000000000000003
julia> @time isprime1(p) # I renamed your function to isprime1
8.941389 seconds (4 allocations: 160 bytes)
true
julia> @time isprime1(p)
8.977674 seconds (4 allocations: 160 bytes)
true
julia> @time isprime(p) # this is the function from the Primes package
0.000163 seconds (4 allocations: 160 bytes)
true
Your input is ~10^35, so you can imagine that it would take a very long time to return.