CODEWITHSUNDEEP
algorithmtestingprimesbrute-force
Matt123
Matt123

Reputation: 615

Finding first n primes efficiently

I have a brute-force algorithm that takes an input n, and displays the first n prime numbers. The code works, but I also have to answer this question:

Give the number of test items that would be required to assure correctness.

Is there a way to calculate this? Would I technically need to test every possible int value (all 2 billion possibilities)?

Upvotes: 1

Views: 141

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76297

If you have a number n, and need to check if it is a prime, there are more efficient ways than brute force.

One way would be to use the Miller-Rabin Primality Test. The Miller-Rabin test either finds proof that a number is a composite, or it does not such find proof (it does not directly prove that a number is a prime). So the scheme would be:

  1. run Miller-Rabin at most k times (or until it found that the number is a composite)

  2. if Miller-Rabin claims it is a possible prime, perform a brute force check

Miller-Rabin runs as follows. Obviously, you need test only for odd n, and so n - 1 is even, and you can write n - 1 = 2sd for some positive s and positive odd d. Randomly choose an a from the range (0, n - 1). If ad ≠ 1 | n and a2rd ≠ -1 | n, then n is a composite.

If n is a composite, the probability that k iterations of Miller-Rabin will not prove it so, is less than 4-k. Note that by the Prime Number theorem, primes are scarce.

The computational-complexity of k applications of Miller-Rabin, even with a naive implementation, is, is O(k log3(n)).

Upvotes: 2

Related Questions