有什么方法可以更快地生成元素并检查它们是否为素数？

Question

我有一个任务，这是要求

Write a program that finds the number of the prime numbers in a randomly 
generated row.

No more than 100 examples are set to the standard input. Each 
example is defined by two positive integers s and N per row (s <10^3, N <10^9). 
s sets a numerical row (by srand (s)) of length N, which is generated with 
rand ()% 1000.

Print out the count of all prime numbers.

我目前将此作为我的代码，在我的 PC 上，最大值需要 3 秒才能找到数字行中所有素数的计数。

#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

bool isPrime(int num) {
   if (num <= 3) {
     return num > 1;
 } else if (num % 2 == 0 || num % 3 == 0) {
    return false;
 } else {
     for (int i = 5; i * i <= num; i += 6) {
         if (num % i == 0 || num % (i + 2) == 0) {
             return false;
         }
     }
     return true;
 }
}

int main()
{
int seed;

long long lenght;

while(cin >> seed >> lenght){

    srand(seed);

    unsigned long long totalPrimes = 0;

    for (int i = 0; i < lenght; ++i) {

        int prime = rand() % 1000;

        if (isPrime(prime)) {
            totalPrimes++;
        }
    }

    cout << totalPrimes << endl;

    int seed = 0;

    int lenght = 0;

 }


 return 0;
}

问题是这似乎没有他想要的那样快。有没有更快的方法？我尝试了很多东西，但都比我上面的代码慢。

Answer 1

您可以进行算法改进

"All programming is an exercise in caching." -Terje Mathisen

所以为什么要不止一次计算素数呢，存起来看看生成的随机数是不是其中一个，线性搜索或者二分查找都可以

如果您运行遍历所有数字一次以找到质数并将其存储在索引数组中，这样您就可以在 O(1) 而不是 O(log N) 中进行查找

if (primeList[x])
  totalPrimes++;

有什么方法可以更快地生成元素并检查它们是否为素数？

Any way to generate elements faster and check if they are prime?

c++

variable-assignment