Is it OK to use the probabilistic approach we learned to acquire the i-th prime number (namely, the is_prime function) since we proved that it is very unlikely for it to make mistakes?
Yes. And if your auto-test fail for that reason, you'll get the points back and sent to fill out a lottery form…
The probabilistic approach will show that 561 = 3*11*17 is prime (charmichel number ) and its not what we want no ?
How many witnesses you sample? if 100, this is highly unlikely.
[For reference only: http://en.wikipedia.org/wiki/Fermat_primality_test#Flaw .
A Carmichael number m will cause Fermat's test to pass only for witnesses a that are not strange to m. In your example, these are only numbers that are not multiplies of 3, 11, or 17 - highly unlikely for a sample of size 100 ]
I got the output 8 for some reason.
This question is not very intuitive and a bit hard to debug. Do you have any recommendations on how to try and look for the errors.
when i input the other examples that were written in the HW and test - it works.
Is 1 prime in this question?
In the lecture we defined a function that checks if you are prime and 1 wasn't prime.
can I write my own is_prime function(runs on O(n**0.5)) and not use the one in the lecture?
if i use the is_prime function from the lectures do i need to leave it in the sekeleton file or to assume it exists?
Is it OK to change the number of iterations of is_prime from 100 to a lower number, to make sure computation time does not exceed 10 seconds ? It seems like 0.2550 and even 0.2540 is small enough for our purposes.
yes, this sounds reasonable (but not much lower).
On my computer 100 samples run in less than 10 seconds though.
I ran it 100 times on my computer and the average was ~10 seconds
The 10-seconds condition here is not so good, a friend's code runs on his computer in 3 seconds, and on my computer in ~ 15 secs.
Not sure about Shriber computers, but I would suggest raising the bar over 10 seconds to avoid inconsistency like that.
My guess is that an inefficient implementation would take a lot more than 10 seconds…
The 10 second condition is specifically made for Shriber computers, so any inconsistency between other computers does not matter.
can i assume the probabilistic is prime will work for all the first 5432 primes (because it will surely fail afterall there are some numbers which act like prime numbers and there is at least one in that range). but if i use regular check it will take forever surely more than 10 seconds.