d2jsp
Log InRegister
d2jsp Forums > Off-Topic > Computers & IT > Programming & Development > Basic Prime Number Generator
Add Reply New Topic New Poll
Member
Posts: 4,841
Joined: Jan 16 2008
Gold: 0.00
Apr 1 2013 07:09am
Hey :)

So I need a prime number generator and this is what I came up with:

Code
class primeexample
{
   public static void main (String[] args)
   {
   int n=3, divisor=2;
   double mod;
   boolean prime=true;

   System.out.println(n-1);
   while(true)
       {  
       while(divisor<n)
           {
           mod=n%divisor;  
           if(mod==0)
               {
               prime=false;
               }
           divisor=divisor+1;
           }
       if (prime==true)
       {
       System.out.println(n);
       }
       n=n+1;  
       divisor=2;
       prime=true;
       }
   }
}


My question is, with the proneness to errors of "double==x" statements, how can I find out for what values of n the program will stop working accurately? Second question is whether the mod==0 statement is avoidable (where mod is a double).
Member
Posts: 4,841
Joined: Jan 16 2008
Gold: 0.00
Apr 1 2013 07:54am
too late to edit my post, but an improvement would be adding "&& prime==true" to the while(divisor<n) loop condition.

This post was edited by tt_toby on Apr 1 2013 07:56am
Member
Posts: 1,241
Joined: Jun 25 2011
Gold: Locked
Apr 1 2013 08:16am
Ok first there's something else you can do that'll speed up the algorithm.
n is prime IFF n is not dividable by any number below or equal to sqrt(n) (so you should have while(divisor<=sqrt(n) ) (do some research for a proof).
Don't know when this algorithm will give wrong values, but since n is an int, I think you should at least stop the program when n=2147483647 or declare n as a double if you want to go higher.
As for your last question, I don't understand what you mean exactly?

This post was edited by m0hawk on Apr 1 2013 08:18am
Member
Posts: 4,841
Joined: Jan 16 2008
Gold: 0.00
Apr 1 2013 08:33am
Thanks. I meant that (very large n)/(n-1) will eventually give mod values not equal to zero but so small that mod will be rounded down to 0, even with mod being a double. Not sure if this is solved by the sqrt(n) approach. This requires divisor to be a double, however.
Member
Posts: 1,241
Joined: Jun 25 2011
Gold: Locked
Apr 1 2013 08:54am
Quote (tt_toby @ Apr 1 2013 04:33pm)
Thanks. I meant that (very large n)/(n-1) will eventually give mod values not equal to zero but so small that mod will be rounded down to 0, even with mod being a double. Not sure if this is solved by the sqrt(n) approach. This requires divisor to be a double, however.


you mean (very large n)%(n-1) right? the modulus operation gives the remainder of the division so it will always be an integer number, why should it be so small as to be rounded to 0 ?

This post was edited by m0hawk on Apr 1 2013 08:55am
Member
Posts: 13,425
Joined: Sep 29 2007
Gold: 0.00
Warn: 20%
Apr 1 2013 12:18pm
Quote (tt_toby @ Apr 1 2013 09:09am)
Hey :)

So I need a prime number generator and this is what I came up with:

Code
class primeexample
{
   public static void main (String[] args)
   {
   int n=3, divisor=2;
   double mod;
   boolean prime=true;

   System.out.println(n-1);
   while(true)
       {  
       while(divisor<n)
           {
           mod=n%divisor;  
           if(mod==0)
               {
               prime=false;
               }
           divisor=divisor+1;
           }
       if (prime==true)
       {
       System.out.println(n);
       }
       n=n+1;  
       divisor=2;
       prime=true;
       }
   }
}


My question is, with the proneness to errors of "double==x" statements, how can I find out for what values of n the program will stop working accurately? Second question is whether the mod==0 statement is avoidable (where mod is a double).



you can change it to

Code
if((n%divisor)==0)
Member
Posts: 1,241
Joined: Jun 25 2011
Gold: Locked
Apr 1 2013 12:36pm
Quote (AbDuCt @ Apr 1 2013 08:18pm)
you can change it to

Code
if((n%divisor)==0)


Obviously, but I don't think that's what he meant tbh ^^
Member
Posts: 13,425
Joined: Sep 29 2007
Gold: 0.00
Warn: 20%
Apr 1 2013 02:11pm
Quote (m0hawk @ Apr 1 2013 02:36pm)
Obviously, but I don't think that's what he meant tbh ^^


when he stated "avoidable" i would imagine he meant able to remove it from code. no clue what else he could mean by that
Go Back To Programming & Development Topic List
Add Reply New Topic New Poll