Google recruit problem, exp and prime
Find the first prime number of 10 consecutive digits in the base e of the natural logarithm. However, e uses only up to 200 digits (it appears by then).
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190
Put this in a text file and read it from the program
def prime?(n)
(2..Math::sqrt(n).to_i).each do |i|
if n % i == 0
false
break
end
true
end
end
exp = File.read('napier.txt').delete('.')
digit = 10
(0..exp.length).each do |i|
slice_dig = exp.slice(i, digit).to_i
if prime?(slice_dig)
puts slice_dig
break
end
end
The 1st to 9th lines are the primality test method prime? Divide the number little by little as 2,3, & # x2026; If it's divisible, it's not a prime number. If it's not divisible, it's a prime number.
Lines 11 and 12 read the file. e 200 digits are put in napier.txt. Decimal point is an obstacle to processing, so delete it.
The 14th to last lines are for e-splitting Primality test is performed by cutting out the 200-digit e while shifting it one by one from the beginning.
Implemented almost according to the lecture page
The execution result looks like this.
7427466391
note
-In the program part that performs primality test, the description of the loop range is Math :: sqrt (n) .to \ _i + 1. 　(2..n-1).each do |i|Calculation time is faster than.Speed ​​up because the number of loops is reduced It's self-evident, but I wasn't sure why the loop to Math :: sqrt (n) .to \ _i + 1 was fine. ・ By the way, this problem seems to be Google's recruitment problem.