# Prime number solver.

• May 30th, 2012, 02:34 PM
Danny123
Prime number solver.
Good day. I want to create a program to calculate prime numbers up to an integer limit. I am extremely new to Java ( I'm on hour 13 of Sam's teach yourself Java in 24 hours), so bear with me.

I have established that I must find the factors of a number, then deduce that if the only factors are 1 and the number itself, then i must print that number. After much trial and error, I have given up. My code has changed considerably, and I have added new sections on after every error i received, however now when I run the file, there is simply no output. The requirements for printing the prime number are not being fulfilled, it may be a problem with the loops or the array. Apologies for the messy code.

Code :

```class Primes { public static void main(String[] args) {   // Factors of a number - if the only ones on that list are 1 and the // nunber itself then print it.   for (int number = 1; number <= 10; number++) { for (int counter = 1; counter < number; counter++) { int factor = number / counter; int remainder = number % counter;   int factorArray[] = new int[10];   if (remainder == 0) { factorArray[counter] = factor; }   if (counter == number) { for (int newCounter = 1; newCounter < 10; newCounter++) { int newFactor = 0; newFactor = newFactor + factorArray[newCounter]; if (newCounter == 9) { if (newFactor == (number + 1)) System.out.println(number); } } }   }   } } }```
• May 30th, 2012, 03:16 PM
Norm
Re: Prime number solver.
You have a lot of loops and if tests. What are they all for? Why do the loops use 9 & 10 as end points? What is the array for?
It looks like you wrote a bunch of code without doing a design first. Can you make a list of the steps that the code should do to solve the problem? When you get a logical list of steps, then try writing the code for them.
• May 30th, 2012, 05:04 PM
Parranoia
Re: Prime number solver.
Just a helpful bit of information, the maximum number of loops required for finding a prime number is the square root of that number. Then really after that you just need to check if the number in your loop is divisible by your counter variable. To do this you can use the modulus operator. So for instance if your number % counter is equal to zero, the number is not prime; else continue on, incrementing your counter variable.
• May 31st, 2012, 05:56 AM
Danny123
Re: Prime number solver.
@ Norm. Yes i did not think about a design before writing the code, it is something I need to start doing. I have written the logical list of steps:

1: Loop through some numbers up to a certain limit ( in this case I put it as 10 )

2: Find all of the Factors of the current number in the loop

3: Determine that if the only factors of that number are 1 and the current number, display that number.

The array was used to hold the current factors of the number. The newCounter loop was designed to loop through the array elements, and add them to the newFactor variable. If newFactor variable was equal to 1, plus the number itself, then it is a prime number and must be printed. Does this make sense?

@ Parranoia. If I understand you correctly, my loop should look like this.

for (int counter = 1; counter < number.(sqrt function here); counter++)
• May 31st, 2012, 07:36 AM
Norm
Re: Prime number solver.
If the variable: number is the counter of prime numbers you want to find, why is it used anywhere else in the code? It should only count the number of prime numbers found.
Quote:

2: Find all of the Factors of the current number in the loop
What variable contains the "current number"?
• May 31st, 2012, 11:59 AM
Parranoia
Re: Prime number solver.
Quote:

Originally Posted by Danny123
@ Norm. Yes i did not think about a design before writing the code, it is something I need to start doing. I have written the logical list of steps:

1: Loop through some numbers up to a certain limit ( in this case I put it as 10 )

2: Find all of the Factors of the current number in the loop

3: Determine that if the only factors of that number are 1 and the current number, display that number.

The array was used to hold the current factors of the number. The newCounter loop was designed to loop through the array elements, and add them to the newFactor variable. If newFactor variable was equal to 1, plus the number itself, then it is a prime number and must be printed. Does this make sense?

@ Parranoia. If I understand you correctly, my loop should look like this.

for (int counter = 1; counter < number.(sqrt function here); counter++)

You are correct, sir :)
• May 31st, 2012, 03:34 PM
Danny123
Re: Prime number solver.
@ Norm. I want to print out the prime numbers, not the amount of them calculated. The variable number ( which is declared in the very first for loop ) holds each number that may or may not be a prime. The code is ran through for number = 1, then it is incremented and ran through for number 2 etc.
• May 31st, 2012, 05:36 PM
Norm
Re: Prime number solver.
This part was confusing:
Quote:

program to calculate prime numbers up to an integer limit
Is the number the max value for a prime number or the number of prime numbers you want to find?
In pseudo code:
Code :

```begin loop i = 1 to number if i is prime save i end loop   vs   cnt=0 nbr = 1 while cnt <= number if nbr is prime { save nbr cnt++ } nbr++ end loop```
• May 31st, 2012, 06:54 PM
Danny123
Re: Prime number solver.
@ Norm. I apologize for not wording it correctly. I will try my best to convey it to you. I want to have a list of numbers, ( 1 to 10 in this case ) and I want to pick out the primes from this list, and print each one. I do not want to find the total number of primes, or their max value. I simply want to print out what numbers are prime from a given list.

Looking at your Pseudo code is interesting. You state if i is prime. Could you possibly tell me how to tell if a number is prime? That is want I want to do. ( In my code I figured that a number must be prime, if the sum of the factors of that number only add up to 1 + that number )
• May 31st, 2012, 08:07 PM
Norm
Re: Prime number solver.
I would ask Google how to determine if a number is prime.
• May 31st, 2012, 08:33 PM
javapenguin
Re: Prime number solver.
If a number has a factor other than one or itself, then it's not prime.

Basically
if number % otherNumber = 0 and otherNumber !=1 and otherNumber != number, then it's not prime.
• May 31st, 2012, 10:27 PM
aesguitar
Re: Prime number solver.
Quote:

Originally Posted by javapenguin
If a number has a factor other than one or itself, then it's not prime.

Basically
if number % otherNumber = 0 and otherNumber !=1 and otherNumber != number, then it's not prime.

That method is inefficient though. I've been running a program for over an hour calculating the sum of every prime number up to 10,000,000,000 using that method. I'm stuck with it because of the range limitations of an int but for what he's looking into, try studying a little bit of sieving. It's incredibly fast, all the primes up to 2000000 in .07 seconds, vs about .8 seconds I think while using that brute force method.
• May 31st, 2012, 10:53 PM
copeg
Re: Prime number solver.
Quote:

Originally Posted by aesguitar
That method is inefficient though. I've been running a program for over an hour calculating the sum of every prime number up to 10,000,000,000 using that method. I'm stuck with it because of the range limitations of an int but for what he's looking into, try studying a little bit of sieving. It's incredibly fast, all the primes up to 2000000 in .07 seconds, vs about .8 seconds I think while using that brute force method.

...for instance, Sieve of Eratosthenes - Wikipedia, the free encyclopedia
• June 1st, 2012, 09:51 AM
Danny123
Re: Prime number solver.
@ Norm. I know what prime numbers are, don't be so cheeky.

@ Javapenguin. Thank you. otherNumber !=1 and otherNumber != number. This is the code i needed. Can I ask you if my method is still viable though. ( If the sum of all the factors of number are only equal to 1 + number, then number is a prime ).
• June 1st, 2012, 10:01 AM
Norm
Re: Prime number solver.
My response was to this question:
Quote:

Could you possibly tell me how to tell if a number is prime?
Have you found how to do it?
• June 1st, 2012, 12:17 PM
Danny123
Re: Prime number solver.
Then I apologize. I was under the impression that you thought I did not know what a prime was. I think I know the algorithm now.

Find the factors of a number ( by using if number % otherNumber = 0 ).
Then say if otherNumber !=1 and otherNumber != number.
That means the number is not prime.
• June 1st, 2012, 12:18 PM
Norm
Re: Prime number solver.
No problem. I don't have the algorithm in my head and have to look it up if I need one.
• June 4th, 2012, 05:30 AM
vijaykamma
Re: Prime number solver.
check this code..... it may helpfull....

class Primes {
public static void main(String[] args) {
int num = 10;
System.out.println("Prime numbers below number"+num+" are:");
for (int number1 = 1; number1 <= num; number1++) {
int count = 0;
for (int number2 = 1; number2 <= number1; number2++) {
if (number1 % number2 == 0)
count++;
}
if (count < 3)
System.out.print(number1 + " , ");
}
}
}