Trial Division Loop Problem
Hello everybody!
I've been working on trial division loop problem and I hit a dead end :(
Before I write about how I attempted to the problem before coming here, I have to show you guys the problem.
THE PROBLEM-------------------------------
Find and print out the eight prime integers between 99,900 and 99,999 using trial division (testing divisibility by possible factors). Write two nested loops: The outer loop will iterate over the 100 numbers being tested for primeness; the inner loop will check potential factors, from 2 up to the square root of the large dividend number (don't worry about which ones are or aren't prime). Use the modulo operator % to test for divisibility, and stop testing factors — cut the inner loop short — after finding one. Example: the first dividend to test is 99,900; its potential factors run from 2 to 316. Since ( 99900 % 2 == 0 ), it is not prime, so do not check factors 3 and higher, but exit the inner loop and go directly to processing 99,901.
--------------------------------------------
SO TO TACKLE THIS PROBLEM.
Thanks for jps for the advice on writing out the steps.
1. I set the min value to 99900 and the max value to 99999 and my outer loop will iterate for 100 times.
2. The outer loop also has to test for primeness so I wrote an "if statement" to check for divisibility and if it is divisible by 2, a continue statement to end
that loop and to continue to the next one.
3. I wrote the inner loop to test for factors by trial division.
4. Loop goes wrong and won't print the prime numbers.. anybody have any ideas on whats wrong?
Heres my loop:
Code Java:
/* This program is designed to find and print out the eight prime integers between 99,900 and
99,999 using trial division*/
// instructions = write two nested loops
// the outer loop will iterate over the 100 numbers being tested for primeness
// the inner loop will check potential factors from 2 up to the square root of the large dividend numbers.
// This program will use % to test for divisibility
public class assignment7
{
public static void main(String args[])
{
// The two numbers
int divider = 2;
int min;
int max = 99999;
// Loop iteration of the 100 numbers
for(min = 99900; min < max; min++)
{
for(divider = 2; divider <= Math.sqrt(min); divider++)
{
if(min % divider == 0)
{
continue;
}
System.out.println("Prime: "+ min);
}
}
}
}
any ideas or advice?
Re: Trial Division Loop Problem
Sort the problem out into steps.
Code :
from m=Min to Max
test m for prime
if m is found to not be prime during tests, stop testing m and move to m+1
otherwise all tests failed, m must be prime, PRINT m OR SAVE m FOR PRINTING LATER ON
The caps part marks the place in your loops where you would remember or print a prime number.
Re: Trial Division Loop Problem
Quote:
Originally Posted by
jps
Sort the problem out into steps.
Code :
from m=Min to Max
test m for prime
if m is found to not be prime during tests, stop testing m and move to m+1
otherwise all tests failed, m must be prime, PRINT m OR SAVE m FOR PRINTING LATER ON
The caps part marks the place in your loops where you would remember or print a prime number.
Thanks for the reply!
I understand the steps you gave me.. but is there a way in java where you can assign a variable a certain range?
you put m = Min to Max
Re: Trial Division Loop Problem
Quote:
Originally Posted by
Wwong3333
you put m = Min to Max
The direct answer to the question is no.
What I wrote up is pseudo code. That line would refer to the portion of your code where you set a for loop to run from 99900 to 99999, where Min=99900 and Max=99999. Using m as the "current number up for evaluation" as the loop progresses. So first cycle m=99900. Second cycle m=99901. ...and so on.
Re: Trial Division Loop Problem
Quote:
Originally Posted by
jps
The direct answer to the question is no.
What I wrote up is pseudo code. That line would refer to the portion of your code where you set a for loop to run from 99900 to 99999, where Min=99900 and Max=99999. Using m as the "current number up for evaluation" as the loop progresses. So first cycle m=99900. Second cycle m=99901. ...and so on.
Ahh! pseudocode. Thanks for the steps you wrote down for me. I wrote an outer loop that runs from 99900 to 99999, and wrote a inner loop to test for primeness. However it goes wrong, and debugging is giving me major headaches.. any tips on how to fix it?
Re: Trial Division Loop Problem
Quote:
Originally Posted by
Wwong3333
I wrote an outer loop that runs from 99900 to 99999,
Nice. Does it work? This looks like a good place to do a println(indexOfTheLoop) just to make sure it prints 99900, 99901, 99902, ..., 99999 before moving on.
Quote:
Originally Posted by
Wwong3333
and wrote a inner loop to test for primeness.
Nice. Does this part work? Yet another stop-to-test-point the way I see it. You could println(allNumbersFoundToBePrime) just to have a list to compare and see that you are getting only primes, and all primes. There are many lists of prime numbers available through your favorite search engine to compare to.
Quote:
Originally Posted by
Wwong3333
However it goes wrong,
That does not sound good. But other than that, it does not tell us much.
Quote:
Originally Posted by
Wwong3333
any tips on how to fix it?
Nothing specific. My old eyes can not see your screen from here. Please post your code and error messages when posting a question. You can use comments in code to draw attention to areas you think need attention.
Re: Trial Division Loop Problem
Quote:
Originally Posted by
jps
Nice. Does it work? This looks like a good place to do a println(indexOfTheLoop) just to make sure it prints 99900, 99901, 99902, ..., 99999 before moving on.
Nice. Does this part work? Yet another stop-to-test-point the way I see it. You could println(allNumbersFoundToBePrime) just to have a list to compare and see that you are getting only primes, and all primes. There are many lists of prime numbers available through your favorite search engine to compare to.
That does not sound good. But other than that, it does not tell us much.
Nothing specific. My old eyes can not see your screen from here. Please post your code and error messages when posting a question. You can use comments in code to draw attention to areas you think need attention.
Ah sorry, I'm new to using forums.
Code Java:
// Loop iteration of the 100 numbers
for(min = 99900; min < max; min++)
The outer loop works fine. It iterates 100 times from 99900 to 99999.
However, the problem resides in the inner loop.
Code Java:
for(divider =2; divider <= Math.sqrt(min); divider++)
{
if(min % divider == 0)
{
continue;
}
else
{
System.out.println("Prime number: "min);
}
}
I've tried using while & do-while loops but no output comes out.
I am confused because my program outputs a whole bunch of numbers including even ones. As you are a expert, do you see any errors or flaws within my inner loop? Sorry.. I would try to work it out by myself but I spent 4 hours trying new things and debugging but nothing works..
also not to mention feeling like a complete failure after all that hard work over 30 lines of code =\
Re: Trial Division Loop Problem
Seems to be a syntax error on this line:
System.out.println("Prime number: "min);
I assume that was related to transferring the code to the forum since you said the program prints, and obviously that line will not compile.
Try to break the pseudo code down into smaller steps. When every detail is listed, translating to code will be much easier. What is the output exactly? Compare the output you are getting to the code. What line of code says even numbers are not prime, and should be ignored? If you can step through the code, inserting values in place of the variables, line by line, and see what the code is doing, you will eventually see the point where the code does something that does not match what you thought it would do.
When posting code and questions, it is also a great idea to include the output from your sample run.
