创建一个扩展 class RandomGenerator 的 class PrimeRandomGenerator

Question

我必须创建一个 class 扩展 RandomGenerator 并在每次用户在主程序中输入一个区间时生成一个随机素数。

我已经创建了构造函数和 isPrime 方法，但我不知道下一步该做什么。

我到此为止了。我确定这里有错误，但我看不到它们。

public class RandomGeneratorImproved extends RandomGenerator {
    public RandomGeneratorImproved(int prime) {
        int startp=0;
        int tillp=prime-1;

    }


    public RandomGeneratorImproved(int lowp,int upperp) {
        int startp=lowp;
        int tillp=upperp;

    }


    public boolean isPrime(int startp,int tillp) {
        int prime=rgen.nextInt(startp,tillp);
        int n=0;
        if (prime<=1) {
            return false;
        } else if (prime<=3) {
            return true;
        } else if (prime%2==0 || prime%3==0){
            return false;
        }
        for (int i=5;i<(prime/i);i+=6) {
            if (prime%i==0) {
                return false;
            }
        }
        return true;
    }


    private RandomGenerator rgen= RandomGenerator.getInstance();
}

备注：

如果用户只输入一个数字（比方说：x），那么间隔将为 (0,x)。换句话说，我们必须创建两个方法或两个构造函数。
例如：
public int nextPrime(int n) 或 public int nextPrime(int low,int high)
不允许我使用数组（或其他使问题更简单的现成方法）。
我搜索了所有涉及随机素数生成器的内容，但找不到与此类似的内容。

Answer 1

关于如何改进和使用 class 的一些建议。

I have to create a class that extends RandomGenerator and produces a random prime number each time the user enters an interval in the main program.

这告诉我，您的 class 的实例在创建时并未与范围相关联。该范围仅根据用户生成质数的需求给出。因此，我会

创建一个空的构造函数并在那里进行任何初始化。
添加重载方法 public int generatePrime(int high) 和 public int generatePrime(int low, int high)。通常，具有较少参数（较少数据）的重载方法应该通过完成所需的数据来调用最具体的方法（参见下面的代码）。
方法名称isPrime表明它应该检查给定的单个int是否是素数。我会做到 boolean isPrime(int primeQ).

剩下的唯一一步是找出指定范围内的 int 给 isPrime 的内容。由于 superclass 有一个方法在范围内生成一个随机的 int ，你可以将它传递给 isPrime 来检查它是否是素数。如果是，return它，否则再试一次。请注意，这是效率极低，但由于缺乏工具和信息，这是我能找到的最简单的桥梁。

代码如下：

public class RandomGeneratorImproved extends RandomGenerator {

    private RandomGenerator rgen;

    public RandomGeneratorImproved() {

        rgen = RandomGenerator.getInstance();
    }

    public int generatePrime(int prime) {

        return generatePrime(0, prime - 1);
    }

    public int generatePrime(int lowp, int upperp) {

        int prime = rgen.nextInt(lowp, upperp);
        while (!isPrime(prime))
            prime = rgen.nextInt(lowp, upperp);
        return prime;
    }

    public boolean isPrime(int prime) {

        int n = 0; // <------ this is not used
        if (prime <= 1) {
            return false;
        }
        else if (prime <= 3) {
            return true;
        }
        else if (prime % 2 == 0 || prime % 3 == 0) {
            return false;
        }
        for (int i = 5; i < (prime / i); i += 6) {
            if (prime % i == 0) {
                return false;// "random number"+prime+"is not a prime number";
            }
        }
        return true;// "random number"+prime+"is a prime number";
    }
}

请注意，行 int n = 0; 给出了一个警告，即 n 从未被使用过。您可能想要删除它。

用法为：

RandomGeneratorImproved rpg = new RandomGeneratorImproved();
int generatedPrime = rpg.generatePrime(6, 30);
int generatedPrime2 = rpg.generatePrime(30); // same as rpg.generatePrime(1, 30)

Answer 2

拒绝方法 - 在感兴趣的范围内生成一个随机数，检查它是否满足目标标准并 return 如果它满足则重复该过程 - 具有产生完全无偏见的优点结果。它的缺点是性能（或缺乏性能）。

此外，试验划分几乎是人类已知的最慢的素数测试方法。根据 'random primes' 的使用，不同的方法是可能的。它们都需要达到范围上限的平方根的质因数才能以某种形式提供，但 Trial Division 也是如此。

备选方案 1：埃拉托色尼的窥视孔

鉴于目标范围似乎仅限于小整数，以下方法是可行的：抽取一个随机数 k，使用 windowed Eratosthenes 筛法筛选范围 [max(2, k - 335), k]，然后return 该范围内的最高素数。这是可行的，因为最大 4,302,407,359 的素数之间的差距不超过 336。因此，微小的 window ('peephole') 必须包含一个素数。

缺点：由此产生的素数分布不均匀（有偏差）。例如，如果 k == 2，数字 2 只会被 returned，因为下一个更高的素数 (3) 就在它旁边。相比之下，数字 3,842,610,773 后面跟着 335 个非素数，因此它被抽中的概率是数字 2 的 336 倍。但是，通过查看输出来证明偏差并不容易，并且对于自动化测试人员应该几乎不可能。

警告：在这种情况下，筛选总是需要处理所有素数直到 k 的平方根，这涉及每个素数的模除以计算 window 内的起始偏移量。相比之下，仅根据前十几个素数，Trial Division 就可以拒绝超过 85% 的所有复合材料。因此，在任何情况下，Peepholes 都可能比 Trial Division 有优势。

备选方案 2：懒惰分段的埃拉托色尼

筛选前 2^31 个数字需要相当多的 CPU 时间（在 C++ 中大约 1 CPU 秒，在 Java 中更多），并且其中很多除非需要大量的随机素数，达到数百万，否则努力就会白费。如果只需要极少数随机素数，那么 Trial Division 确实是可行的方法，但如果需要更多，那么分段筛分的惰性方法会有所帮助。

选择一个不超过一级缓存大小的段大小，并创建一个覆盖整个目标范围的段缓存数组。抽取一个随机的k后，从缓存中获取对应段的引用；如果为 nil，则筛选段并将引用存储在适当的缓存槽中。然后你在任何情况下都有一个段引用，所以你可以通过检查段中的位 (k >> 1) % segment_size 来测试 k 的素数，假设只有赔率筛子。

段应该是代表奇数的打包位图，如果段大小是 2 的幂，% segment_size 可以通过掩码计算。这样你总是可以快速得到答案，而不需要长时间等待筛选一次完成整个范围。当你需要它时（即当你绘制大量随机素数时）效率会提高，因为缓存会自行填充，导致越来越多的素数查询被已经存在的段满足。

与 Peephole 方法不同，这给出了一个完全无偏的分布（这有点明显，因为它只取代了素数测试，而不是绘制素数的实际方法）。

post on Code Review 中有更多信息讨论了绘制 100 个随机素数的挑战。

创建一个扩展 class RandomGenerator 的 class PrimeRandomGenerator

Create a class PrimeRandomGenerator that extends class RandomGenerator

java

random

primes

class