Main Thread

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 ]

Just to self-check, what is the answer for mod(5432,11)?

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.

Thank you!

Note that 1 is considered prime is this question.

Is 1 prime in this question?

In the lecture we defined a function that checks if you are prime and 1 wasn't prime.

You are right that 1 is usually not considered prime. However this is mostly a matter of definition.

Since the example considers 1 as prime, please follow this definition.

can I write my own is_prime function(runs on O(n**0.5)) and not use the one in the lecture?

Yes - you may implement different versions of whatever we learned in class, if you need that.

can i use an algorithime that we see in the lecture??!

In general, unless otherwise stated you are allowed to use any algorithm that you saw in class/recitations as long as it is relevant for the solution.

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?

You MUST include it in your file, otherwise our tests will fail on your code.

can I use next_prime function which we saw in the lecture ???

You may always use what you saw in class, unless the question directly forbids.

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.25**50 and even 0.25**40 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…

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.

I assume you are referring to Carmichael numbers.

See my reply to another question on this topic.