# Prime Number finder

• 02-13-2011, 11:06 PM
hoosierfan24
Prime Number finder
Hello i am trying to write a program to find all the prime numbers in a given number range but i cant seem to do it. Here is what i have so far, i think im close but just cant get it right

Code:

``` public class MainClass {  public static ArrayList<Integer> interval( int m, int n )   {     ArrayList<Integer> result = new ArrayList<Integer>();            int a= m-1;       for(int i = m; i<=n; i++ )     {           a++;              result.add(a);         }       return result;   }  public static boolean divides( Integer a, Integer b )   {     return ((b % a) == 0);   } public static ArrayList<Integer> primes( int t ) {   ArrayList<Integer> plist = interval( 2, t );   int m = 0;   while ( m < plist.size() )   {     int n = m;     while ( n < plist.size() )     {       if ( divides( plist.get( m ), plist.get( n ) ) )         plist.remove( n );       else         n++;     }     m++;   }   return plist; } public static void main( String[] args ) {   System.out.println( primes( 20 ) ); }```
• 02-13-2011, 11:14 PM
sunde887
You can do this in a much simpler manner. Try creating a static method which takes some number and determines if it is prime
Code:

`public static boolean isPrime(int n)`
after you do that the problem is fairly trivial, all you will need to do from there is ask for 2 inputs and loop from the one to the other testing isPrime on each.

Also what errors are you getting?

What is interval supposed to do? It seems like it may be a waste.

Is the goal to find all primes from 1 - n? or from n1 - n2?
• 02-13-2011, 11:26 PM
hoosierfan24
interval is accepting to inputed numbers and all numbers in that range are imported into the array list.

and yes i am trying to find the primes from n1-n2

and im not getting any errors i am just not getting the correct prime numbers outputted
• 02-13-2011, 11:35 PM
sunde887
Code:

`if ( divides( plist.get( m ), plist.get( n ) ) )`
When the method reaches this statement, whats m? Whats n?
while filling an arraylist of all the possibles is a decent idea it's a bit overcomplicated.

Whats a prime number? How do you determine them? Also, are you getting compile time errors, or runtime exceptions? Post what they say.

Are you taking into account that when you remove an item from an arraylist all indexes are shifted down?

My biggest piece of advice for you is this, start small when you write your programs, make something fairly basic and move your way up until you reach your goal.

For this problem start by figuring out how to determine if a number is divisible by another, you got that part so you can not determine how to test if a number is prime, do that and post just that code.
• 02-13-2011, 11:44 PM
hoosierfan24
m is currently the first element in the arraylist and n is also the first element in the array list

here is how i would determine a prime number
Code:

```boolean isPrime(int n) {     //check if n is a multiple of 2     if (n%2==0) return false;     //if not, then just check the odds     for(int i=3;i*i<=n;i+=2) {         if(n%i==0)             return false;     }     return true;```
if it is not prime though i also need to take it out of the arraylist. I need to print the the arraylist at the end that only contains the prime numbers in the interval
• 02-13-2011, 11:52 PM
sunde887
now create main, and pass some common prime numbers to your method to make sure it's working correctly(1, 3, 5, 7, 11), and pass some non prime numbers, the more you try the better you can test if you have successfully defined the method. From there you can now create(in main) the interval testing, or you can do it in a separate method.

Why did you choose to use a filled array list?
Are you taking into account that when you remove an item from an arraylist all indexes drop down one?
• 02-14-2011, 12:21 AM
hoosierfan24
ok so i figured it out finally haha

i needed to change the prime class to this
Code:

```public static ArrayList<Integer> primes( int t )   {     ArrayList<Integer> plist = interval( 2, t );     int m = 0;     while ( m < plist.size() )     {       int n = m;       while ( n + 1 < plist.size() )       {         if ( divides( plist.get( m), plist.get( n+1 ) ) )         plist.remove( n + 1 );         else              n++;       }       m++;     }       return plist;   }```
i was just calculating the prime number incorrectly
• 02-14-2011, 12:33 AM
Junky
Interesting.

I would think that only adding prime numbers to a List would be easier than removing non-primes.
• 02-14-2011, 12:46 AM
sunde887
What junky said was what I was hinting out, your approach is unique, and Im glad you solved it, but the simpler way would be to create an empty array list, adding items that are prime.
• 02-14-2011, 12:55 AM
Junky
Mind you OP is kinda doing a sieve of Eratosthenes.
• 02-17-2011, 09:53 AM
k_nica
You'll have to change to what ever method you use to input or output a value. I'm using IO.java.
Other than that, works like a charm.

{{{

public class NthPrime
{
public static void main(String[]args)
{
int count=0;
int numTest=1;
int finalPrime=0;

System.out.println("Enter a value 'N' to find the 'Nth' prime number.");

if(primeN == 0)
{
return;
}

do
{
double limit = Math.sqrt(numTest);
boolean prime = true;

if(numTest==1)
{
prime = false;
}

else if(limit<2)
{
prime=true;
}

else
{
for(int divisor = 2; divisor <= limit && prime; divisor++)
{
if(numTest % divisor == 0)
{
prime = false;
break;
}
/*
else
{
prime=true;
finalPrime = numTest;
}
*/
}
}

if(prime==true)
{
count=count+1;
finalPrime=numTest;
numTest++;
System.out.println("The current prime number stored is: " + finalPrime);
}
else
{
numTest++;
}

}while(count<primeN);

}
}

}}}
• 02-17-2011, 10:13 AM
goldest
Quote:

Originally Posted by k_nica
Other than that, works like a charm.

Hey Hey Hey... There you are!

No Code Tags, No code indentation and spoon feeding with ready baked code.

Everyone here was kind of stuck up for someone to come and do this for OP. And there you arrive.

God is Great...!!! Cheers :D