[Okysho]

I really hate to do this, especially when the problem seems so simple, but I've been cracking at this for two days and nothing I do seems to be working.

The original assignment question is simply to input a number from the user and find the nearest prime number greater than the number input by the user.

So far I've come up with the following:

package pack;

import java.io.*; 
import java.util.*; 
public class Lab1 {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader reader;
		reader = new BufferedReader(new InputStreamReader(System.in)); 
		
		//Declare variables
		String input ;
		int UserNumber = 0;
		int prime = 0;
		boolean yes = false;
		int n1 = 0;
		int n2 = 0;
		//Prompt user.
		System.out.println("Please enter an integer");
		
		
		 // Get input from user, change to integer
		input = reader.readLine();
		UserNumber = Integer.parseInt(input);
		
		prime = UserNumber;
		
		 Random rand = new Random(); 

		 int randomNum = rand.nextInt((prime -1) +1) + 1; 
		 
		while (yes != true) {
		
		
			 
		
		if ((randomNum ^(prime -1)) == (1 % prime)){
			yes = true ;
			
		}
		else{
			yes = false;
			prime++;
		}
		

			}
		
		System.out.println("The first prime number greater than " + UserNumber +" is " + prime);
		
	}
}

I decided to go ahead and use Fermat's little theorem as the basis for my algorithm, but for some reason I can't get the code to output any results that seem even remotely correct.

If I put in 45 (the next available prime should be 47) but my results will constantly vary from infinite loops to arbitrary numbers.

What am I doing wrong?

I've narrowed it down to two possibilities. It's either the way I'm doing the math in the theorem or the randomization function.

Extra info:

Fermat's little theorem states that for any integer a between 1 and p, where p is a prime number, then a^(p-1) == 1 mod p

Please help. I feel stupid

[GregBrannon]

My opinion: you should rethink your approach. The standard test to determine if a number, a, is prime is:

boolean isPrime = true;

for ( int i = 2; i < Math.sqrt( a ); i++ )
{
    if ( ( a % i ) == 0 )
    {
        isPrime = false;
    }
}
return isPrime;

Note: The algorithm above is meant to be pseudo-ish, so it needs adjusting to work.

To implement the above to solve your assignment, begin at the next number after the number entered by the user, checking each until finding the first prime number.

This post has been edited by GregBrannon: 11 September 2011 - 12:23 PM

[Okysho]

Thanks Greg,

I'd come across that test on wikipedia, but I thought I'd take the fancy approach and try Fermat's way... I guess there were too many problems.

I've almost got it working, and have refined (and trimmed) the code down to the following:

package pack;

import java.io.*; 
public class Lab1 {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader reader;
		reader = new BufferedReader(new InputStreamReader(System.in)); 
		
		//Declare variables
		String input ;
		int UserNumber = 0;
		int prime = 0;
		boolean IsPrime = false;
		//Prompt user.
		System.out.println("Please enter an integer");
		
		
		 // Get input from user, change to integer
		input = reader.readLine();
		UserNumber = Integer.parseInt(input);
		
		prime = UserNumber +1;
		
		for ( int i = 2; i < Math.sqrt( prime ); i++ )
		{
		    if ( (prime % i ) == 0 )
			    {
		        IsPrime = false;
		        prime++;
			  }
		    else{
		    	IsPrime = true;
		    }
				}
		
		System.out.println("The first prime number greater than " + UserNumber +" is " + prime);
		
	}
}

For the most part this works, but when I enter in 32 the prime it gives me is 34. This is clearly not correct. It's also doing this for 35, giving 36 when the answer to both numbers should be 37.

Did I implement something wrong?

Also, for my own pride purposes, I wouldn't mind some more feedback on how to fix my fermat version to solve this problem...

[sepp2k]

As Greg said, you should use a different approach, but here are some of the things that are wrong in your code:

1. ^ in java is the xor operator, not the exponentiation operator. For the latter you need Math.pow.

2. 1 % prime will just be equal to 1. To check whether a number is congruent to 1 modulo prime you need to do number % prime == 1, not number == 1 % prime. The latter would be the same as writing number == 1.

3. Either way the approach is wrong. You're assuming that if randomNum to the power of (prime - 1) is congruent to 1 module p for any randomNum, prime must be prime. This not what the theorem says. prime is only prime, if the above is true for all numbers. Since you obviously can't check whether it's true for all numbers, the theorem is useless to you.

4. Another problem is that you're only looking for primes in one direction. I mean when the current number is not prime, you check the next number above it. So once you get your primality test to work, you'll always find the next prime greater than the number the user gave you. But you're supposed to find the closest number, so you need to check the numbers that are lower than the user's numbers as well as the ones that are greater.

Regarding your new code: The loop condition needs to be i <= Math.sqrt( prime ) (<= instead of <). Otherwise it would not try to divide by 3 when testing 9 for example.

Also the fourth point of my previous post still applies.

[Okysho]

That was a big help Sepp2k, but I'd like to argue a few points there.

Fermat's primality test says that this can only be true on the interval (1 < a < p) where a is an integer and p is prime. (hence the condition on the random number.)


http://en.wikipedia...._primality_test

Unless I'm still misinterpreting this information, I'm still failing to see how my approach cannot be expressed through programming. Overly complex? yes, but impossible? I find that hard to believe.

Also, my assignment asks specifically for the first prime greater than the number supplied by the user.

Edit:

Sepp2k. Thanks for that last little bit, but it still spits out 34, when I enter 32, despite having changed the conditional statement to what you suggested. I'm still playing around with it though

This post has been edited by Okysho: 11 September 2011 - 12:56 PM

[sepp2k]

Okysho, on 11 September 2011 - 09:52 PM, said:

http://en.wikipedia...._primality_test

To quote that article:

Quote

The Fermat primality test is a probabilistic test to determine if a number is probable prime.

Edit:

I've just noticed another mistake in your code: After you set isPrime to false, you need to exit the loop immediately. By staying in the loop isPrime can be set to true again later, which you don't want. So break from the loop as soon as you set isPrime to false (or just return false;).

This post has been edited by sepp2k: 11 September 2011 - 12:59 PM

[Okysho]

Ach!! And it was in blue too!! Guess I overlooked that by accident...

Since the main function is void, I cannot have a return statement. How would I break the loop?

[GregBrannon]

You guys . . .

Since you didn't use a method to determine whether the number is prime, you'd have to modify your loop some to get it to work. (Perhaps sepp2k's advice above will help, but I didn't test it.)

Here's an approach I like, because it includes 'parts' you can reuse (I included just the main() and isPrime() methods. Enclose in a class of your choice):

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub

        BufferedReader reader;
        reader = new BufferedReader(new InputStreamReader(System.in)); 

        //Declare variables
        String input ;
        int userNumber = 0;
        int prime = 0;
        //Prompt user.
        System.out.println("Please enter an integer");


        // Get input from user, change to integer
        input = reader.readLine();
        userNumber = Integer.parseInt(input);

        for ( int i = userNumber + 1; ; i++ )
        {
            if ( isPrime( i ) )
            {
                prime = i;
                break;
            }
        }
        
        System.out.println("The first prime number greater than " + userNumber +" is " + prime);

    }
    
    public static boolean isPrime( int prime )
    {
        boolean isPrime = true;
        
        for ( int i = 2; i < Math.sqrt( prime ); i++ )
        {
            if ( ( prime % i ) == 0 )
            {
                isPrime = false;
                break;
            }
        }
        
        return isPrime;
    }

[sepp2k]

Oh, yeah. I was thinking you had the prime-checking logic in its own bool-method. But you don't so, you can't just return. So either just put a break in there (which will break from the surrounding loop) or do put the primality-check into its own isPrime method (which would be a readability win anyway).

[Okysho]

Ok since I don't like copying other people's code (plus I want to keep this all in one function, the problem shouldn't need two...)

I've come up with this:

package pack;

import java.io.*; 
public class Lab1 {

	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader reader;
		reader = new BufferedReader(new InputStreamReader(System.in)); 
		
		//Declare variables
		String input ;
		int UserNumber = 0;
		int prime = 0;
		boolean IsPrime = false;
		//Prompt user.
		System.out.println("Please enter an integer");
		
		
		 // Get input from user, change to integer
		input = reader.readLine();
		UserNumber = Integer.parseInt(input);
		
		prime = UserNumber +1;
		
		prime++;
		
	for (int j = UserNumber +1; ; j++){	
		if(IsPrime = true)
		{
			prime = j;
			break;
		}
		else{
			for ( int i = 2; i <= Math.sqrt( prime ); i++ )
			{
				if ( (prime % i ) == 0 )
					{
					IsPrime = false;
					break;
					}	
				else{
					IsPrime = true;
				}
			}
		}	
	}
		System.out.println("The first prime number greater than " + UserNumber +" is " + prime);
		
	}
}

I took a look at what Greg did and modified it a bit, but I'm still not getting the primes. Instead it just increases the initial value by 1.

does my idiocy know no bounds?

[GregBrannon]

I respect you wanting to get your code right and hope you'll learn something in the process . . . even if we disagree on how many methods there should be.

The code I pasted in below replaces lines 29 - 53 of your code above. My comment line numbers correspond to the code I pasted in below.

Explaining what I did and how it works. Let me know if you have any questions:

Line 3, don't need it. You already added one to the user's input, and the code logic below uses prime as a starting point and increments it to find the next prime.

Line 5 'for' loop: this loop is set up to test all numbers for primacy from one greater than the User's input to infinity, if necessary. Use the variable 'prime' as the beginning point, since you already defined it.
Line 7, adds a flag to signal when the algorithm is done. Start with true, because the logic below will kick out of loops on 'false'. 'true' will keep the machine running, 'false' signals to start over with the next number.
Line 11, if statement that corresponds to your line 34: This if needs to test the current 'j' for primacy. Since you're not using a method() to determine primacy, the test has to be within the if statement. But that will be too complex to have completely in the if statement, so you need to set up another loop before the if statement. We'll use 'i' from 2 to the square root of the User's number + 1, or prime.
Line 9, a new for loop to define which divisors will be used to test 'j' for primacy.
Line 11, now that the primacy test has been set up, test each j with each divisor i. If j is evenly divisible by an i, then j is not prime.
Line 15, break out of the i loop to move to the next j.
Line 18, if the logic gets to here, and isPrime is true, then the algorithm found a prime number. Edit: If isPrime is not true, the test continues with the next j.
Line 22, set prime to the current j
Line 23, break out of the j loop.

        prime = UserNumber +1;
        
//        prime++;
        
        for (int j = prime; ; j++)
        { 
            boolean isPrime = true;
            
            for ( int i = 2; i < Math.sqrt( prime ); i++ )
            {
                if( ( j % i ) == 0 )
                {
                    // j is not a prime number, check the next one in the j loop
                    isPrime = false;
                    break;
                }
            }
            // if it gets to here and isPrime is true, the number being tested,
            // 'j' is prime
            if ( isPrime )
            {
                prime = j;
                break;
            }
        }
        System.out.println( "The first prime number greater than " 
                + UserNumber +" is " + prime );
    }

Edit: minor edits to comments above for clarity/correctness.

This post has been edited by GregBrannon: 11 September 2011 - 02:43 PM

[Okysho]

That was exactly what I was trying to do. Thanks so much!! I'll be doing an in-depth analysis of this soon and take into account everything you've said.

Thank you very much.

[GregBrannon]

I tested more thoroughly, especially for small numbers, and discovered that the test set had to be expanded. Line 9 of my post above should be changed to:

     for ( int i = 2; i <= Math.sqrt( prime ) + 1; i++ )

I think that covers all corner cases.

Edit: Examining the code, I found the real problem. The loop index i should vary from 2 to the square root of j, the number currently being tested, rather than 'prime'. Line 9 of the above should be changed to:

     for ( int i = 2; i <= Math.sqrt( j ); i++ )

This post has been edited by GregBrannon: 11 September 2011 - 05:44 PM

[jon.kiparsky]

for ( int i = 2; i <= Math.sqrt( j ); i++ )

Oi! Invariant! Out of the loop!

double limit = Math.sqrt(j);
for ( int i = 2; i <= limit; i++ )

This post has been edited by jon.kiparsky: 11 September 2011 - 06:23 PM

[FamiHug]

Quote

The original assignment question is simply to input a number from the user and find the nearest prime number greater than the number input by the user.

you can check if input number < 2 -> return 2;
then, you only have to start from 3 and add 2 to each time because all primes are odd, except 2

int limit = (int)Math.sqrt(j);
for ( int i = 3; i <= limit; i = i + 2 )