Computing Prime Numbers
Back to the Program-A-Day homepage
ProblemIt is often very useful to be able to compute prime numbers (e.g. Encryption). Create a program that computes every prime number up to 20 using nested loops. This is a high order calculation, meaning that when calculating a lot of prime numbers you will have to wait some time for it to complete. However, you can experiment with your program and see how long it takes to compute prime numbers up to 1,000, 10,000, or even 1,000,000. Warning: your if you decide to compute a large amount of prime numbers your program may be sitting there for a large amount of time. Output should look like this: |
Getting Started | |
|---|---|---|
SolutionStart by declaring a boolean that will determine if a given number is prime or not. Use a for loop that will count from 2 to 20. Start at 2 for the simple fact that we know 1 is not a prime number but the product of 1 and itself is 1. Everything we do inside this loop will be done on each number. boolean isPrime;
for(int i = 2;i <= 20;i++)
{
}
Since any number is only the product of 1 and itself we need a way to find the sum of all numbers that are less than itself. This will be to ensure that there are no other products that equal that number. We can do this by use of a loop. J will always be less than i since we know that the product of i and 1 is the only way to have a product of i. for(int i = 2;i <= 20;i++)
{
for(int j = 1;j < i;j++)
{
}
}
The next step is to add a third for loop that will represent the second value of the product. To avoid repeating calculations we can say that the new value in the loop k must be less than or equal to k. Since we now have several levels of scope it would also be a good idea if we labeled our closing braces just so we know which is which. for(int i = 2;i <= 20;i++)
{
for(int j = 1;j < i;j++)
{
for(int k = 1;k <= j;k++)
{
} //for k
} //for j
} //for i
In the for k loop we simply place an if statement in regards to each iteration of the loop. Remember, we want to check if our current value of i is the product of any two values that are described by the j and k loops. for(int i = 2;i <= 20;i++)
{
isPrime = true; //number is innocent until proven guilty
for(int j = 1;j < i;j++)
{
for(int k = 1;k <= j;k++)
{
isPrime = false; //this criminal is NOT a prime number
} //for k
} //for j
} //for i
At this point we are almost done. We just need to decide where to print each individual number. Storing them in an array won't work since we, technically, don't know how many there are. We must print them directly in the loop. This is why I mentioned to label the for loops, when closing braces get further apart it can get hard where one level of scope ends in relation to another. } //for k
} //for j
//print out each number if it is prime
if(isPrime)
{
System.out.print(i + " ");
}
} //for i
When adding in other prints to make your work look nice make sure you put them outside of the loops unless you want them printed many times over. boolean isPrime = true; //check to see if it's true
//we will be printing out the numbers later
//we just don't want to have this print in the loop
System.out.print("The prime numbers are: ");
//the for loop for checking each number
//you can omit 1 because it is not a prime number!
for(int i=2;i<=20;i++)
{
If you continue on to other courses such as COMP 2080 (Analysis of Algorithms) you will learn that having 3 loops like this can destroy your programs performance. You will learn various methods, such as recursion, that can be used as an alternative to loops. Computing prime numbers is a very complex computing task. A for loop can be used to iterate through each number you are checking to be prime. Two other loops can calculate the products of every combination of numbers below the one you are checking to be prime. The if statement determines if the number is ultimately prime. To avoid storing values for printing later you can put the print method right into the loop and perform the printing from there. That is how you compute prime numbers with nested loops. | ||
Code | ||
