您正在检查 25 9 = 3,814,697,265,625 个数字是否为素数。这是很多主要测试，而且总是需要很长时间。即使在所有数组条目 (in m) 为 0 的最佳情况下（对于性能而言）（不要介意测试将 0 视为素数），因此试除循环永远不会运行，它也需要数小时才能运行。当 的所有条目m都是正数时，代码将运行数百或数千年，从那时起，每个数字将被超过 50,000,000 个数字试除。
看着素数支票，
check_prime = 1;
for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
check_prime = 0;
}
第一个明显的低效率是，即使在找到除数并num建立复合性之后，循环也会继续。知道结果后立即跳出循环。
check_prime = 1;
for ( y = 2; y <= num/2; y++)
{
if ( num % y == 0 )
{
check_prime = 0;
break;
}
}
在不幸的情况下，您测试的所有数字都是素数，这不会改变任何事情，但如果所有（或几乎所有，对于几乎足够大的值）数字都是复合的，它将减少运行时间的一个因素至少5000。
接下来的事情是你分成num/2. 那是没有必要的。为什么你停在num/2，而不是num - 1？好吧，因为您发现 的最大真除数num不能大于num/2因为 if (num >) k > num/2、 then2*k > num和num不是 的倍数k。
这很好，不是每个人都能看到。
但你可以进一步追寻这种思路。如果num/2是 的除数num，则表示num = 2*(num/2)（使用整数除法，除 外num = 3）。但是然后num是偶数，它的复合性已经由除以2决定了，所以除以num/2成功就永远不会尝试。
那么需要考虑的最大除数的下一个可能候选者是什么？num/3当然。但如果那是 的除数num，那么num = 3*(num/3)（除非num < 9）和除以 3 已经解决了这个问题。
继续下去，如果k < √num和num/k是 的除数num，那么num = k*(num/k)我们看到它num有一个更小的除数，即k（可能甚至更小）。
所以的最小非平凡除数num小于或等于√num。因此循环只需要运行y <= √num, 或y*y <= num。如果在该范围内没有找到除数，num则为素数。
现在问题出现了是否循环
for(y = 2; y*y <= num; ++y)
或者
root = floor(sqrt(num));
for(y = 2; y <= root; ++y)
第一个需要在每次迭代中对循环条件进行一次乘法，第二个需要在循环外计算平方根。
哪个更快？
这取决于平均大小num以及许多是否为素数（更准确地说，取决于最小素数除数的平均大小）。计算平方根比乘法花费的时间要长得多，为了补偿该成本，循环必须运行多次迭代（平均而言）——“很多”是指超过 20、超过 100 还是超过 1000 取决于。num大于，10^8就像这里可能的情况一样，计算平方根可能是更好的选择。
现在我们已经将试验除法循环的迭代次数限制为复合√num或num素数，并将运行时间减少至少 5000 倍（假设所有m[index] > 0，所以总是num >= 10^8），无论测试数字中有多少素数. 如果大多数取值num是素数较小的组合，则缩减因子要大得多，以至于通常运行时间几乎完全用于测试素数。
通过减少候选除数的数量可以获得进一步的改进。如果num能被 4, 6, 8, ... 整除，那么它也能被 2 整除，因此num % y对于偶数永远不会产生 0 y > 2。这意味着所有这些划分都是多余的。通过特殊的大小写 2 并以 2 的步长递增候选除数，
if (num % 2 == 0)
{
check_prime = 0;
} else {
root = floor(sqrt(num));
for(y = 3; y <= root; y += 2)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}
}
要执行的分区数和运行时间大致减半（假设有足够多的坏情况，偶数的工作可以忽略不计）。
现在，只要y是 3 的倍数（除了 3 本身），num % y只会在num不是 3 的倍数时计算，所以这些除法也是多余的。您也可以通过特殊情况 3 来消除它们，并且y只让运行不能被 3 整除的奇数（从 开始y = 5，交替递增 2 和 4）。这会砍掉大约三分之一的剩余工作（如果存在足够多的坏情况）。
继续这个消除过程，我们只需要除以不超过num的素数√num来确定它是否是素数。
所以通常最好找到不超过num您要检查的最大值的平方根的素数，将它们存储在一个数组中并循环
root = floor(sqrt(num));
for(k = 0, y = primes[0]; k < prime_count && (y = primes[k]) <= root; ++k)
{
if (num % y == 0)
{
check_prime = 0;
break;
}
}
除非最大值num足够小，例如，如果您num < 2^31总是num有2^31位占用256 MB，如果你只有奇数的标志[需要特殊情况检查是否num是偶数]，你只需要128 MB来检查< 2^31常数时间内数字的素数，进一步减少所需空间因为筛子是可能的）。
到目前为止，主要测试本身。
如果m数组包含可被 2 或 5 整除的数字，则可能值得重新排序循环，将循环用于i最外层，如果可被 2 或 5 整除，则跳过内部循环m[i]- 所有其他数字都乘以幂在添加之前为 10，因此num将分别是 2 的倍数。5 而不是素数。
但是，尽管如此，运行代码仍然需要很长时间。九个嵌套循环散发着错误设计的味道。
你想做什么？也许我们可以帮助找到正确的设计。