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

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);
            }
        }
                  }  
 
        }
 
    }
    }
}

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.

@ 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++)

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

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

@ 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 )

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.

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.

@ 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 ).

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.