时间戳

首页 > 解决方案 > 素数分解如何保证因子是素数？

c# - 素数分解如何保证因子是素数？

问题描述

在这个特定的代码中，它如何不输出 6 1，因为 6 除以 18 没有余数。

int n = 18;
int[] fact = new int[100];
int[] pow = new int[100];
int d = 0; 

for (int i = 2; i <= n; i++) 
{
    int s = 0;

    while(n % i == 0)
    {
        s++; 
        n /= i;
    } 

    if (s > 0)
    {
        fact[d] = i; 
        pow[d] = s;
        d++; 
    }
}

标签： c#primes

解决方案

每个数字要么是素数，要么是素数的倍数。看：https ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

如果它不能被一个素数整除，它也不能被那个素数的任何倍数整除。因为 18 可以除以 2 - 4, 6, 8, 10，而其他一切都不需要测试。由于 19 不能除以 2、4、6、8 和 10 永远不需要测试。20 可以被 10 整除，永远不需要测试。它已经除以 2，所以我们当时排除了一半可能的数字。

我们本能地排除除数，但通常只针对 2 - 仅测试奇数 - 但您可以更进一步。由于除法的结果也必须是素数或素数的倍数，我们甚至可以在通过平方根后停止。

你真正需要的是一个完整的素数列表，直到素数> Squarroot（PrimeCandidate）。没有从记忆中阅读它，这是我知道的最快的方法。

实际上，我不久前就该主题写了一些东西，关于检查素数的 5 种方法：https ://social.msdn.microsoft.com/Forums/en-US/85fc2406-d2e9-495a-bea7-e516661f8b40 /primal-issues-multithreading-lists-in-memory-and-checking-for-prime-number?forum=csharpgeneral

推荐阅读