通过调用另一个方法随机素数方法

Question

我很难弄清楚这个程序。我已经制定了一个方法来确定输入的数字是否是素数，但现在我必须编写一个方法，以正整数作为参数，并返回[0，num-1]范围内的随机素数。我不确定我是否正确地使用了isPrime方法。此外，我还必须通过在主体中调用它来测试这个方法，但我也不确定如何做到这一点。这是我的代码：

public static boolean isPrime(int num)
{
    for(int i = 2; i<= num-1;i++)
    {
        if (num % i == 0)
        {
            return false;
        }        
    }
    return true;
}
public static int randomPrime(int num)
{
    Random r = new Random();
    int x = r.nextInt(num);
    for( int i = 0; i <= x; i++)
    {
        if(!isPrime(x))
        {
            num = x;
        }
    }
    return x;
}

Answer 1

这不是一种有效的方法。我建议你构建一个Eratosthene筛，然后随机选择一个。

以下是我的做法：

public static Random rd = new Random(System.currentTimeMillis());
public static int randomPrime(int num) {
    Boolean[] sieve = new Boolean[num+1];
    sieve[0] = true;
    sieve[1] = true;
    for (int i=2 ; i<num.length ; i++)
       if (!sieve[i])
           for (int j = 2*i ; j<num.length ; j += i) 
                sieve[j] = true;
    List<Integer> primes = new LinkedList<>();
    for (int i=0 ; i<sieve.length ; i++) 
        if (!sieve[i]) primes.add(i);
    return primes.isEmpty() ? -1 : primes.get(rd.nextInt(primes.size());
}

Answer 2

如果要检查x在randomPrime方法中是否为素数，为什么要在0 <= i <= x上调用isPrime？您正在检查0和x之间（包括0和x）是否有素数。这不是你想要的。

我认为这应该在不大幅改变算法的情况下为你完成任务。注意：根据您的随机数生成器和种子值，此代码可能需要很长时间才能终止，并且实际上不能保证终止。（考虑一下你的随机数生成器只生成复合数的情况。）

public static int randomPrime(int num)
{
    Random r = new Random();
    int x = r.nextInt(num);
    while(!isPrime(x))
    {
        x = r.nextInt(num);
    }
    return x;
}

更新：

用这样的东西测试它：

public static void main(String[] args)
{
    int N = 42;
    int x = randomPrime(N);
    System.out.println(x);
}