[jacobsnakob94]

I'm fairly new to programming, so please don't be too mean if my code is poorly structured or nonsensical!

I'm attempting problem 7 on Project Euler. It is asking for the 10,001th prime number. Now, in my head I have a good idea on how to tackle this one systematically, but I'm having a hard time translating this into code. My method for finding this prime number is this (please tell me if there are any flaws in my logic!):

Any number that is not prime can be broken up into smaller prime numbers. Thus, if some number n cannot be divided evenly into any of the prime numbers smaller than it, then n must be a prime number. With that being said, one could identify the 10,001th prime number by starting at 2, adding 1 (3), and checking to see if this number can be divided evenly by 2. Since 3 cannot be divided evenly by 2, it is also prime and can be added to the "prime list". Then the next number, 4, could be checked by dividing it by 2 and 3. Since it can be divided by at least one of these numbers (2), then it is not prime. Then 5 would be checked, and since it cannot be evenly divided by 2 or 3, it is prime and would be added to the list. This process would continue until 10001 prime numbers are present in the list, and the final one would be the answer.

I know that was probably an unnecessary explanation, but I wanted to give a clear explanation of my intention behind writing my code. So..here it is:

package find.a.prime.number;
import java.util.Scanner;
public class FindAPrimeNumber {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[] numberOfprimes = new int[10001];
        numberOfprimes[0] = 2;
        int test = 3;
        int numberIndices = 0; 
        int b = 0; 
        int a = 0;
        
        while(numberIndices <= 10001){
            while(b <= numberIndices){
               if(test%numberOfprimes[b]!= 0){
                   if(b == numberIndices){
                       numberOfprimes[b] = a;
                       numberIndices = numberIndices + 1;
                   }
                   b = b + 1;
                   
               }
               else{
                   test = test + 1;
                   break;
               }
            }
            b=1;
            
        }
        
        System.out.println("The 10,001st prime number is " + test);
        
    }
}

Alright, so here are my two questions..
1) Am I even approaching this correctly? If not, feel free to nudge me in the right direction. And by nudge, I do not mean "give me the answer". I'd like to figure this out on my own.
2) When I compile this program, it says that I can't "divide by zero" on the line "if(test%numberOfprimes[b] != 0){". Why is it doing that? When does numberOfprimes[b] ever equal zero?

Thanks in advance for taking your time reading this! And again, try not to judge me too harshly! I just started learning this a couple days ago, so I'm still very much a novice..
-Jacob

This post has been edited by jacobsnakob94: 02 October 2011 - 07:00 PM

[fromTheSprawl]

The variable b in your main method declaration isn't accessible inside that while statement. So it assumes that b is local inside that while loop and doesn't have a value.

By the way, why not use for loops?

[jacobsnakob94]

fromTheSprawl, on 02 October 2011 - 07:07 PM, said:

The variable b in your main method declaration isn't accessible inside that while statement. So it assumes that b is local inside that while loop and doesn't have a value.

By the way, why not use for loops?

Well, to answer your question, I'm kind of learning this on a "learn-new-things-as-I-need-them" basis. I just learned the basics and started doing problems on Project Euler from there, researching new things as I go. I didn't even know how to write arrays and such before this particular problem. So, I haven't looked into for-loops, but if they would provide a better alternative, then I'm more than willing to learn now!

[pbl]

You make it complicated for nothing...
and actually discussed one of the most discussed algorithm

here is an easy one (not tested)

public class Prime {

	public static void main(String[] arg) {
		int[] firstPrime = new int[1000];
		firstPrime[0] = 2;
		firstPrime[1] = 3;
		int primeFound = 2;
		
		for(int i = 5; i < 9999999; i += 2) {
			int j = 1;
			for(; j < primeFound; ++j) {
				if(i % firstPrime[j] == 0) {
					break;
				}
			}
			if(j == primeFound) {
				firstPrime[primeFound++] = i;
				if(primeFound == firstPrime.length) {
					System.out.println("The " + firstPrime.length + "th prime is: " + i);
					break;
				}
			}
			
		}
		
	}
}

but the ultimate one is there

http://www.dreaminco...-prime-numbers/

[macosxnerd101]

I used the Sieve of Eratosthenes to do this, and just generated additional numbers if I found myself lacking. So if I found all the primes between 2-10000 and found myself only having 1000 primes, I'd add numbers from 10001-12000 (as an example) to the List and sieve those. Repeating until I had 10001 primes. You may find an ArrayList helpful here.

Some tutorials you may find helpful from Locke:
Looping
ArrayLists vs. Static Arrays

[burakaltr]

Here's an Alternative one

import java.util.Scanner;

public class Primer{
	
	public static void main(String args[]){
		boolean bool;
		int i,j;
		while(true){
		int min=0,max=100000000;	{
	    int n=0,k=0;	
	//	while(true){
 //	System.out.println(" Enter min , max")	;
	Scanner in=new Scanner(System.in);
	System.out.println(" Enter N for the nth PRIME");
	k=in.nextInt();
//		min=in.nextInt();
//		max=in.nextInt();
		if(min<0)min=1;
		if(min==0)min=min+1;
	
		for(i=min;i<max+1;i++)
		
		{
			bool=false;
		 
		if(i==1)i++;
		for(j=2;j<i;j++)
		{
			
	if(i%j==0){bool=true;
	if(i==2)break;
	
	break;	}
		if(bool==true)
		{
			i++;
			
		}	
		}
		
		if(bool==false)
			
		{
			n++; 
			System.out.println(i+" is a Prime ");	
			
			if(n==k)
			{
			System.out.println(" The Prime "+n+ " th Prime is :"+i);	
			break;
			}
		}
		}
		
		}
}}

}

[jacobsnakob94]

macosxnerd101, on 02 October 2011 - 07:35 PM, said:

I used the Sieve of Eratosthenes to do this, and just generated additional numbers if I found myself lacking. So if I found all the primes between 2-10000 and found myself only having 1000 primes, I'd add numbers from 10001-12000 (as an example) to the List and sieve those. Repeating until I had 10001 primes. You may find an ArrayList helpful here.

Some tutorials you may find helpful from Locke:
Looping
ArrayLists vs. Static Arrays

Ooh! That is interesting! I've never heard of the Sieve of Eratosthenes! I think I will try this method . Thanks for the help!

[macosxnerd101]

A note that the Sieve of Eratosthenes generates primes from 2-n. But it's a good place to start. Glad I could help!

[pbl]

burakaltr please indent your code correctly, it is nightmare to read

import java.util.Scanner;

public class Primer{

	public static void main(String args[]){
		boolean bool;
		int i,j;
		while(true){
			int min=0,max=100000000;	{
				int n=0,k=0;	
				//	while(true){
				//	System.out.println(" Enter min , max")	;
				Scanner in=new Scanner(System.in);
				System.out.println(" Enter N for the nth PRIME");
				k=in.nextInt();
				//		min=in.nextInt();
				//		max=in.nextInt();
				if(min<0)min=1;
				if(min==0)min=min+1;

				for(i=min;i<max+1;i++)
				{
					bool=false;

					if(i==1)i++;
					for(j=2;j<i;j++)
					{
						if(i%j==0){bool=true;
						if(i==2)break;

						break;	}
						if(bool==true)
						{
							i++;

						}	
					}

					if(bool==false)
					{
						n++; 
						System.out.println(i+" is a Prime ");	

						if(n==k)
						{
							System.out.println(" The Prime "+n+ " th Prime is :"+i);	
							break;
						}
					}
				}

			}
		}}

}

And this code is actually much more complicated than the original OP post
and
for(i=min;i<max+1;i++)
no need to test all even number, i +=2 would be a lot more efficient

This post has been edited by pbl: 02 October 2011 - 07:51 PM

[burakaltr]

pbl, on 02 October 2011 - 07:46 PM, said:

Please indent your code correctly, it is nightmare to read

import java.util.Scanner;

public class Primer{

	public static void main(String args[]){
		boolean bool;
		int i,j;
		while(true){
			int min=0,max=100000000;	{
				int n=0,k=0;	
				//	while(true){
				//	System.out.println(" Enter min , max")	;
				Scanner in=new Scanner(System.in);
				System.out.println(" Enter N for the nth PRIME");
				k=in.nextInt();
				//		min=in.nextInt();
				//		max=in.nextInt();
				if(min<0)min=1;
				if(min==0)min=min+1;

				for(i=min;i<max+1;i++)
				{
					bool=false;

					if(i==1)i++;
					for(j=2;j<i;j++)
					{
						if(i%j==0){bool=true;
						if(i==2)break;

						break;	}
						if(bool==true)
						{
							i++;

						}	
					}

					if(bool==false)
					{
						n++; 
						System.out.println(i+" is a Prime ");	

						if(n==k)
						{
							System.out.println(" The Prime "+n+ " th Prime is :"+i);	
							break;
						}
					}
				}

			}
		}}

}

And much more complicated than the original OP post
and
for(i=min;i<max+1;i++)
no need to test all even number, i +=2 would be a lot more efficient

Yes, thank you.

I was experimenting.

Thanks again for the suggestion.

[jacobsnakob94]

I got it all figured out . Thank you all for the help!

[macosxnerd101]

Glad we could help!