1

我有一系列随机数。范围实际上由用户确定，但最多为 1000 个整数。它们被放置在这个：

vector<int> n

并且值是这样插入的：

srand(1);

for (i = 0; i < n; i++)
  v[i] = rand() % n;

我正在创建一个单独的函数来查找所有非质数。这就是我现在所拥有的，但我知道这是完全错误的，因为我在这个系列中得到了素数和复合数。

void sieve(vector<int> v, int n)
{
  int i,j;

  for(i = 2; i <= n; i++)
     {
        cout << i << " % ";
        for(j = 0; j <= n; j++)
           {
              if(i % v[j] == 0)
                 cout << v[j] << endl;
           }
     }
}

这种方法通常在我只有从 0 到 1000 的一系列数字时有效，但是当我的数字乱序和重复时，它现在似乎不起作用。有没有更好的方法来查找向量中的非素数？我很想创建另一个向量，用 n 个数字填充它，然后以这种方式找到非素数，但这会效率低下吗？

好的，由于范围是 0-1000，我想知道创建 0-n 排序的向量是否更容易，然后使用筛子找到素数，这是否更接近？

void sieve(vector<int> v, BST<int> t, int n)
{
  vector<int> v_nonPrime(n);
  int i,j;
  for(i = 2; i < n; i++)
      v_nonPrime[i] = i;

  for(i = 2; i < n; i++)
     {

        for(j = i + 1; j < n; j++)
           {
              if(v_nonPrime[i] % j == 0)
                 cout << v_nonPrime[i] << endl;
           }
     }
}
4

9 回答 9

9

在这段代码中：

if(i % v[j] == 0)
  cout << v[j] << endl;

您正在测试您的索引以查看它是否可以被 v[j] 整除。我认为你的意思是反过来做，即：

if(v[j] % i == 0)

现在，您正在打印 i 的随机除数。您没有打印出已知不是素数的随机数。此外，您的输出中会有重复项，也许没关系。

于 2008-10-29T21:26:29.790 回答
4

首先，我认为 Knuth 首先说过：过早的优化是许多 bug 的原因。先做慢版本，然后想办法让它变快。

其次，对于您的外部循环，您实际上只需要转到 sqrt(n) 而不是 n。

于 2008-10-29T21:15:08.440 回答
2

基本上，你有很多不相关的数字，所以对于每一个你都必须检查它是否是素数。

如果您事先知道数字的范围，则可以生成该范围（或其平方）内可能出现的所有素数，并测试容器中的每个数字是否可被任何一个生成的素数整除。

生成素数最好由 Erathostenes Sieve 完成——该算法的许多示例都可以找到。

于 2008-10-29T21:14:58.673 回答
1

您应该尝试使用初筛。您需要知道创建筛子的 最大数量O(n)（O(max_element)O(1000) == O(1)

于 2008-10-29T21:14:12.530 回答
1

您的代码完全错误。首先，您正在测试 i % v[j] == 0，这是倒数的，也解释了为什么您会得到所有数字。其次，您的输出将包含重复项，因为您正在测试并在每次未通过（损坏的）可分性测试时输出每个输入数字。

其他建议：

使用 n 作为向量中的最大值和向量中的元素个数是令人困惑且毫无意义的。您不需要传入向量中的元素数量 - 您只需查询向量的大小。而且您可以相当快地计算出最大值（但如果您提前知道它，您也可以将它传递给它）。

如上所述，您只需要测试到 sqrt(n) [其中 n 是 vecotr 中的最大值]

您可以使用筛子生成直到 n 的所有素数，然后从输入向量中删除这些值，如上所述。这可能会更快更容易理解，尤其是如果您将素数存储在某个地方。

如果您要单独测试每个数字（我猜是使用反筛），那么我建议按顺序单独测试每个数字。恕我直言，它比您编写它的方式更容易理解 - 测试每个数字是否可被 k < n 整除以不断增加 k。

于 2008-10-29T21:29:15.930 回答
0

您尝试实施的筛子的想法取决于您从质数 (2) 开始并删除该数字的多个这一事实 - 因此，预先排除了依赖于质数“2”的所有数字。

这是因为所有非素数都可以分解为素数。而素数不能用模 0 整除，除非你将它们除以 1 或它们自己。

所以，如果你想依赖这个算法，你需要一些手段来真正恢复算法的这个属性。

于 2008-10-29T21:15:47.330 回答
0

您的代码似乎有很多问题：

  1. 如果你想测试你的数字是素数还是非素数，你需要检查 v[j] % i == 0，而不是反过来
  2. 您没有检查您的号码是否自行划分
  3. 你不断地一次又一次地检查你的号码。这是非常低效的。

正如其他人建议的那样，你需要做一些像埃拉托色尼筛子这样的事情。

因此，您的问题的伪 C 代码将是（我尚未通过编译器运行此代码，因此请忽略语法错误。此代码仅用于说明算法）

vector<int> inputNumbers;

// First, find all the prime numbers from 1 to n
bool isPrime[n+1] = {true};
isPrime[0]= false;
isPrime[1]= false;
for (int i = 2; i <= sqrt(n); i++)
{
  if (!isPrime[i])
    continue;
  for (int j = 2; j <= n/i; j++)
    isPrime[i*j] = false;
}

// Check the input array for non-prime numbers
for (int i = 0; i < inputNumbers.size(); i++)
{
   int thisNumber = inputNumbers[i];
   // Vet the input to make sure we won't blow our isPrime array
   if ((0<= thisNumber) && (thisNumber <=n))
   {
      // Prints out non-prime numbers
      if (!isPrime[thisNumber])
         cout<< thisNumber;
   }
}
于 2008-10-29T21:40:27.733 回答
0

首先对数字进行排序可能是一个好的开始 - 您可以在 nLogN 时间内完成。这是对您的另一个问题的一个小补充（我认为） - 找出一个数字是否是素数。
（实际上，使用这样的一小组数字，您可以使用向量/集合大小的副本更快地进行排序并进行哈希/桶排序/其他）

然后我会找到集合中的最高数字（我假设这些数字可以是无界的 - 在你排序之前不知道上限 - 或者单次通过以找到最大值）

然后用筛子去 - 正如其他人所说

于 2008-10-29T21:43:00.880 回答
0

杰里米是对的，基本问题是你的i % v[j]而不是v[j] % i.

试试这个：

void sieve(vector<int> v, int n) {
  int i,j;

  for(j = 0; j <= n; j++) {
    cout << v[j] << ": ";

    for(i = 2; i < v[j]; i++) {
      if(v[j] % i == 0) {
        cout << "is divisible by " << i << endl;
        break;
      }
    }

    if (i == v[j]) {
      cout << "is prime." << endl;
    }
  }
}

这不是最优的，因为它试图除以小于的所有数字，v[j]而不是仅仅达到 的平方根v[j]。它正在尝试除以所有数字，而不仅仅是素数。

但它会起作用。

于 2008-10-29T22:26:23.367 回答