Thread: 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:

 
/* 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?

Originally Posted by jps

Sort the problem out into steps.

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

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?

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.

// 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.

 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 =\