Question

Nested loop program used to find prime numbers between 2 to 100

Answer 1

Answer:

Of course, the naive ( simple) way, is simply to have two loops. In the inner loop, test if you can divide a number by 2 to n-1. For example, take 11.

11 / 2, is not evenly divisible ( has a non integral answer, and a non 0 remainder)

11/ 3…nope

…

11 / 10…nope

So 11 is prime.

The “fancy” way is using the sieve of erosthonenes ( sp?). You create an array of the numbers, 2 to 100 is fine.

Starting from 2, “mark” every other number ( and not marking 2. You could just set them to 0. So 4, 6, 8, … etc. are marked not prime. Then goto the next unmarked number, and repeat.

I will give an example of 2 to 20.

start with 2, mark all numbers that are a multiple of 2 but don’t mark 2. 2 is unmarked ( it’s prime.)

Then 3, marking 6, 9, …

Then 5, then 7.

When we check 11, we realize the first number to mark is 22, but that’s out of bounds, so we are done marking numbers.

That will give us the unmarked numbers: 2, 3, 5, 7, 11, 13, 17 and 19.