Find the first prime number with 10 consecutive digits at the base e (up to 200 digits) of the natural logarithm. Use the following as input as exp.txt.
2.71828182845904523536028747135266249775
7247093699959574966967627724076630353547
5945713821785251664274274663919320030599
2181741359662904357290033429526059563073
81323286279434907632338298807531952510190
First, primality test. Since a prime number has a divisor of 1 and only that number, if a certain number n is not divided by 2 to n-1, n is a prime number.
The input is stored in the array exp, and exp [0] to exp [9] are treated as one integer. Set the primality test as a method and judge whether exp [0] to exp [9] are prime numbers. If it is not a prime number, slide it one and try with exp [1] to exp [10]. If a prime number is found by repeating this, output.
def prime_judge(num)
for i in 2..num - 1
if num % i == 0
return false
end
end
return true
end
exp = gets.to_s.chomp.delete(".")
for i in 0..exp.length - 10
num = exp[i..i + 9].to_i
if prime_judge(num)
puts num
break
end
end
If you use
> ruby google_recruit.rb < exp.txt
7427466391
I was able to output correctly, but it took a long time. I thought it would take, but I'm still worried, so I put Time.now before and after processing and measure the processing time.
> ruby google_recruit.rb < exp.txt
7427466391
"Processing time 332.1757855s"
About 5 and a half minutes & # x2026;
There is a programming problem with primality testing, and someone is doing it! Ask Google Sensei with "Primality test speeding up" in a straightforward manner.
-Primality test speedup -Fastest Primality Test C # Java C ++
Refer to the area. The judgment method is as follows
Let's implement it. Code below
def prime_judge(num)
if num < 2
return false
elsif num == 2 && num == 3
return true
elsif num % 2 == 0
return false
end
num_sqrt = Math.sqrt(num).floor(0)
3.step(num_sqrt,2) do |i|
if num % i == 0
return false
end
end
return true
end
start_time = Time.now
exp = gets.to_s.chomp.delete(".")
for i in 0..exp.length - 10
num = exp[i..i + 9].to_i
if prime_judge(num)
puts num
break
end
end
p "processing time#{Time.now - start_time}s"
When I try to use it
> ruby google_recruit.rb < exp.txt
7427466391
"Processing time 0.0030629s"
Why is "a multiple of an odd number (3 or more) less than the square root of n is not a prime number" in the first place? It can be expressed as n = a × b when a number n is not a prime number. If both a and b are made as large as possible while satisfying n = a × b, then a = √n and b = √n. That is, at least one of a and b must be less than or equal to √n. This makes it possible to determine whether it is a prime number simply by examining whether it is divisible by the square root of n or less.
In the pre-acceleration program, when a certain number num is not a prime number, it cannot be determined that it is not a prime number without looping num-2 times. However, after speeding up, it can be judged that it is not a prime number in a loop of √num times. Since all the inputs this time are 10 digits, the difference between num-2 times and √num times is large, and we can feel the speedup.