Find the first prime number of 10 consecutive digits with e (base of natural logarithm) read in text.
It's simple to do. Read the character string, cut out the character string by 10 digits from the front, and judge whether it is a prime number or not.
First, create a text (exp.txt) that describes e up to 200 digits, and load it.
def read_exp
exp1=gets.to_s.chomp
end
exp1 = read_exp()
It seems that the string is now read as an array in exp1. As a test
puts exp1[0..9]
To output the 0th to 9th columns of the array
> ruby google_recruit.rb exp.txt
> 2.71828182
#+end_src ruby
Oh, I see, 2 and periods are also in the array, so I have to write the program in consideration of that<br>
By the way, if I try to run it while I'm in the next higher directory, it will exp.Even though I specified the relative path to txt, "exp".There is no txt, "he said, and the work stopped for three days. Is that the case even though I specified the relative path based on the current directory? I thought it was a mystery
#+begin_src ruby
for i in 0..189
num = exp1[2+i..11+i].to_i
puts num
end
end
The initial value outputs the 2nd to 11th of the array, and after that, it can be repeated 190 times to extract 10 digits at a time. When I actually took it out, it was output 10 digits from the head properly. For the time being, I was able to cut out 10 digits at a time, so next I will judge whether this is a prime number.
According to the definition of a prime number, that is, if you divide by 2 other than your own number and reach the end without being divisible, that is the answer.
def prime?(num)
(2..num-1).each do |i|
if num % i == 0
puts i
return false
end
end
return true
end
Divide each do from 2 to your own -1 in order, and if there is a timing that is divisible somewhere, false = not a prime number is returned. Returns true if it is not divisible at all. Create a function like this and take the steady method of calling it every 10-digit number to make something that works for the time being.
for i in 0..189
num = exp1[2+i..11+i].to_i
answer = prime?(num)
if answer == true
puts num
break
end
end
Although it is basic, since a character string is stored in exp1, if you do not add to \ _i to make it an integer, you will not be able to calculate it when you pass it to prime ?. It took me an hour to notice it and I got stuck. If you don't work intermittently, you'll be absorbed in knowing that it's inefficient.
After that, just put the return value of prime? In answer and display it if it is true = prime number.
> ruby google_recruit.rb exp.txt
> 2.71828182
Apparently the correct answer was derived.
But there is actually a tremendous amount of time between these two lines. I knew it would take some time, but it took me 15 minutes to move it while outputting the progress. When I thought that it would take time like a computer, it was Magimon's "time".
To be clear, just judging whether it is a prime number or not is a problem if you are in a state where "it takes a long time to finish, so please have tea in the meantime". So I will try to speed it up.
According to the textbook, to speed up. It seems good to set the loop range of prime? To 2..Math :: sqrt (n) .to \ _i + 1
def prime?(num)
(2..Math::sqrt(num).to_i+1).each do |i|
if num % i == 0
return false
end
end
return true
end
This alone took 15 minutes, but now the answer comes out in an instant. Why is it?
For example, if num = 400, the loop range is 2..21. It used to be 2..399, but by taking the square root, it becomes about 1/20. Similarly
--100000: 2..317-> About 0.3% --50000000: 2..7072-> About 0.1% --3000000000: 2..54773-> About 0.002%
So, the larger the num, the greater the degree of shortening. It is thought that this made it possible to significantly increase the speed.
The reason why the loop range can be up to the square root of num is that if num is n × m, n or m is always less than or equal to the square root of num. Isn't this the case?
So google please give me a job offer. Or just give me a salary.