Can someone explain the "Sieve of Eratosthenes" to me. I'm a bit confused on what I am suppose to do. Is it just printing out 1 to max using for loops?
Create a program to find all the prime numbers between 1 and max . This time, use a classic method called the ”Sieve of Eratosthenes.”
Essentially, you create a list of numbers, 2 to max.
Then, you iterate over the numbers.
If the number is in the list, check all the multiples of the number.
If any there are any multiples of the number in the list, remove them.
If you removed any multiples, you move onto the next number in the list that hasn't been removed.
If you didn't remove any multiples, then all numbers that have not been removed from the list are prime.
Yes, the algorithm is basically correct, as long as the user enters a small number (n <= 100).
The only flaw is that 1 is not prime.
Is there a way to do this without using an array?
No. Well, it doesn't necessarily have to be an array -- some other structures could work (although many would perform worse), but all prime sieves start with a large collection of possibilities and "filter-out" candidates that are eliminated.
In general, there is no easily-computable implicit or explicit formula for prime numbers that we know of.