Prime numbers finder

Question

So I'm trying to make a method that finds a random prime number from 0 to n(inputed from user) using the RandomGenerator class from the acm.utils package and for some reason it doesn't work! I've thought it through lots of times and I think this solution is right, bot it ends up giving numbers that are not wrong!

This is for a project at the uni and I have to use only acm.util! no scanners! only this kind of code

public int nextPrime(int n){
    int num = rgen.nextInt(1, n);   
    boolean prime=false;
    if (num==1){
        return (num);
    }else{
        int i = 2;
        int c = 0;
        while ((i < num-1)&&(prime=false)){
            if( (num % i) == 0){
                c=c+1;
            }
            if((c==0)&&(i==(num-1))){
                prime=true;
            }
            if(c>=1){
                num = rgen.nextInt(1, n);
                i=1;
            }
        i=i+1;
        }
    }
    return (num);
    }

Possible duplicate of [Calculating and printing the nth prime number](http://stackoverflow.com/questions/9625663/calculating-and-printing-the-nth-prime-number) — Abdelhak, Dec 24 '15 at 18:09
Small point: 1 is not a prime. I believe you may have meant to check `if (num == 2) { return num;}`. This would be unnecessary though on account of check in while. — Monkeygrinder, Dec 24 '15 at 18:38

RockAndRoll · Answer 1 · 2015-12-24T18:29:59.423

1

= is for assignment and == is for comparison. You need to change your condition

while ((i < num-1)&&(prime=false)){

to

 while ((i < num-1)&&(prime==false)){ or
 while ((i < num-1)&&(!prime)){

edited Dec 24 '15 at 18:29

answered Dec 24 '15 at 18:22

RockAndRoll

2,247
2
16
35

Or `!prime`, since `prime` is a boolean. – Teepeemm Dec 24 '15 at 18:28

score 1 · Answer 2 · answered Dec 25 '15 at 22:42

Here is a basic method to determine if a number is prime or not. This method is really only meant to understand the logic behind finding if a number is prime or not. Enjoy.

public boolean isPrime()
{
boolean prime = true;

    for (int s = 2; s < original; s++)
    if (original % s != 0 )
    {
        prime = true;

    }
    else
    {
        prime = false;
        return prime;
    }

    return prime;

score 0 · Accepted Answer · answered Dec 24 '15 at 19:15

Your code is rather bizarre. Variable like c is not very clear, and the name doesnt help.

You could read other implementations.

I made some change to make it work. Traces help too !

public static int nextPrime(int n)
    {
    int num = (int)(1+Math.random()*n);  // other generator

 // TRACE HERE
    System.out.println("START:"+num);

    boolean prime=false;

    // CHANGE HERE
    if (num==2)
        {
        return (num);
        }   
        else
        {
        int i = 2;
        int c = 0;

        // CHANGE HERE
        while ((i < num-1)&&(prime==false))
            {
            // Not prime => next one
            if( (num % i) == 0)
                {
                // TRACE HERE
                System.out.println("YOU LOSE: :"+num+" divided by "+i);

                c=c+1;
                } 

            if((c==0)&&(i==(num-1)))
                {
                prime=true;

                // TRACE HERE
                System.out.println("BINGO:"+num);

                // CHANGE HERE
                break;
                }

            if(c>=1)
                {
                // SAME PLAYER LOOP AGAIN
                num = (int)(1+Math.random()*n);

                // TRACE HERE
                System.out.println("RESTART:"+num);

                i=1;

                // CHANGE HERE
                c=0;
                }
        i=i+1;
        }
    }
    return (num);
    }

score 0 · Answer 4 · answered Dec 24 '15 at 19:42

Either you have misstated the problem or else you have not come close to coding the problem correctly. There are 4 prime numbers up to 10: {2,3,5,7}. If the user enters 10, should you give a random prime from this set, or a random one of the first 10 primes {2,3,5,7,11,13,17,19,23,29}? You said the problem was the first interpretation (where 11 would not be a valid response to 10) but you implemented an attempt at the second interpretation (where 11 would be a valid response to 10).

There is a simple way to generate a prime number uniformly within the primes in the range [1,1000000], say. Choose a random integer in the range and test whether it is prime. If so, return it. If not, repeat. This is called rejection sampling. It is quite complicated to get a uniformly random prime number without rejection sampling, since it's not easy to count or list the prime numbers in a large range. It is relatively easy to test whether a number is prime, and for n>1 it only takes about log n samples on average to find a prime in [1,n].

Prime numbers finder

4 Answers4