计算数字最大素数的最佳方法是什么？
我认为最有效的方法如下：
查找可以清楚地划分的最低质数
检查除法结果是否为质数
如果没有，找到下一个最低的
转到2。
我基于这个假设，因为它更容易计算出小的素因数。 这是对的吗？ 我还应该考虑其他什么方法？
编辑：我现在意识到，如果有两个以上素数在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2将失败，因此需要递归算法。
再次编辑：现在我意识到它仍然可以工作，因为最后找到的素数必须是最高的素数，因此，对步骤2中非素数结果的任何进一步测试都将产生较小的素数。
这是我所知道的最佳算法(在Python中)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list |
在最坏的情况下(当输入是质数时)，上述方法在O(n)中运行。
编辑：
下面是O(sqrt(n))版本，如注释中所建议。这里是代码，再次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list |
实际上，有几种更有效的方法来查找大数的因子(对于较小的数，试法师工作得相当好)。
如果输入数具有两个非常接近平方根的因子，那么一种非常快的方法称为Fermat因式分解。它利用恒等式N =(a + b)(a-b)= a ^ 2-b ^ 2，并且易于理解和实现。不幸的是，它通常不是很快。
分解最长100位数字的最著名方法是二次筛。另外，算法的一部分很容易通过并行处理完成。
我听说过的另一种算法是Pollard的Rho算法。它的效率一般不如Quadratic Sieve，但似乎更易于实现。
一旦决定如何将数字分解为两个因子，这就是我能想到的最快的算法，可以找到一个最大的素数：
创建一个优先级队列，该队列最初存储数字本身。每次迭代时，您将从队列中删除最高编号，然后尝试将其分为两个因素(当然，不允许1成为这些因素之一)。如果此步骤失败，则该数字为素数，并且您有答案！否则，您将两个因素添加到队列中并重复。
我的答案是基于三联画的，但对此做了很多改进。基于以下事实：除了2和3外，所有质数均采用6n-1或6n + 1的形式。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| var largestPrimeFactor;
if(n mod 2 == 0)
{
largestPrimeFactor = 2;
n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
largestPrimeFactor = 3;
n = n / 3 while(n mod 3 == 0);
}
multOfSix = 6;
while(multOfSix - 1 <= n)
{
if(n mod (multOfSix - 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
if(n mod (multOfSix + 1) == 0)
{
largestPrimeFactor = multOfSix + 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
multOfSix += 6;
} |
我最近写了一篇博客文章，解释了该算法的工作原理。
我敢冒险，一种不需要测试原始性(也不需要筛子构造)的方法，其运行速度会比使用那些方法的速度更快。如果真是这样，这可能是最快的算法。
JavaScript代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
| 'option strict';
function largestPrimeFactor(val, divisor = 2) {
let square = (val) => Math.pow(val, 2);
while ((val % divisor) != 0 && square(divisor) <= val) {
divisor++;
}
return square(divisor) <= val
? largestPrimeFactor(val / divisor, divisor)
: val;
} |
用法示例：
1
| let result = largestPrimeFactor(600851475143); |
这是代码示例：
类似于@Triptych的答案，但也有所不同。在此示例中，不使用列表或字典。代码是用Ruby编写的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
else
i += 1
end
end
return i
end
largest_prime_factor(600851475143)
# => 6857 |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| //this method skips unnecessary trial divisions and makes
//trial division more feasible for finding large primes
public static void main(String[] args)
{
long n= 1000000000039L; //this is a large prime number
long i = 2L;
int test = 0;
while (n > 1)
{
while (n % i == 0)
{
n /= i;
}
i++;
if(i*i > n && n > 1)
{
System.out.println(n); //prints n if it's prime
test = 1;
break;
}
}
if (test == 0)
System.out.println(i-1); //prints n if it's the largest prime factor
} |
所有数字都可以表示为质数的乘积，例如：
1
2
| 102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89 |
您可以通过简单地从2开始并继续除以直到结果不是您的数字的倍数来找到它们：
1
| 712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1 |
使用此方法，您不必实际计算任何素数：基于您已经将所有前面的数字尽可能多地分解为数字的事实，它们都将是素数。
1
2
3
4
5
6
7
8
9
| number = 712;
currNum = number; // the value we'll actually be working with
for (currFactor in 2 .. number) {
while (currNum % currFactor == 0) {
// keep on dividing by this number until we can divide no more!
currNum = currNum / currFactor // reduce the currNum
}
if (currNum == 1) return currFactor; // once it hits 1, we're done.
} |
最简单的解决方案是一对相互递归的函数。
第一个函数生成所有素数：
首先列出所有大于1的自然数。
删除所有非素数。也就是说，没有素数的数字(除了它们本身)。见下文。
第二个函数以递增顺序返回给定数N的素数。
列出所有素数(见上文)。
删除所有不是N因素的数字。
N的最大素数是第二个函数给出的最后一个数字。
该算法需要具有按需调用语义的惰性列表或语言(或数据结构)。
为了澄清起见，以下是Haskell中上述方法的一种(无效的)实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| import Control.Monad
-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
-- Gives the prime factors of its argument
primeFactors = factor primes
where factor [] n = []
factor xs@(p:ps) n =
if p*p > n then [n]
else let (d,r) = divMod n p in
if r == 0 then p : factor xs d
else factor ps n
-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors |
加快速度只是更聪明地检测哪些数字是质数和/或N的因数，但是算法保持不变。
我知道这不是一个快速的解决方案。希望以更容易理解的缓慢发布方式发布。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static long largestPrimeFactor(long n) {
// largest composite factor must be smaller than sqrt
long sqrt = (long)Math.ceil(Math.sqrt((double)n));
long largest = -1;
for(long i = 2; i <= sqrt; i++) {
if(n % i == 0) {
long test = largestPrimeFactor(n/i);
if(test > largest) {
largest = test;
}
}
}
if(largest != -1) {
return largest;
}
// number is prime
return n;
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
| n = abs(number);
result = 1;
if (n mod 2 == 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i == 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result) |
有一些多余的模测试，因为如果所有因子2和3都被删除，则n永远不能除以6。您只能为i设置素数，这在其他几个答案中也有显示。
您实际上可以在此处缠绕Eratosthenes的筛子：
-
首先创建整数列表
到sqrt(n)。
-
在for循环中标记所有倍数
我直到新的sqrt(n)为止
素数，然后使用while循环。
-
将我设置为下一个素数
名单。
另请参阅此问题。
我正在使用将数字除以当前素数的算法。
我在python 3中的解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def PrimeFactor(n):
m = n
while n%2==0:
n = n//2
if n == 1: # check if only 2 is largest Prime Factor
return 2
i = 3
sqrt = int(m**(0.5)) # loop till square root of number
last = 0 # to store last prime Factor i.e. Largest Prime Factor
while i <= sqrt :
while n%i == 0:
n = n//i # reduce the number by dividing it by it's Prime Factor
last = i
i+=2
if n> last: # the remaining number(n) is also Factor of number
return n
else:
return last
print(PrimeFactor(int(input()))) |
输入：10
输出：5
输入：600851475143
输出：6857
通过从数字中删除所有主要因素的Python迭代方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def primef(n):
if n <= 3:
return n
if n % 2 == 0:
return primef(n/2)
elif n % 3 ==0:
return primef(n/3)
else:
for i in range(5, int((n)**0.5) + 1, 6):
#print i
if n % i == 0:
return primef(n/i)
if n % (i + 2) == 0:
return primef(n/(i+2))
return n |
使用筛子的素数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <bits/stdc++.h>
using namespace std;
#define N 10001
typedef long long ll;
bool visit[N];
vector<int> prime;
void sieve()
{
memset( visit , 0 , sizeof(visit));
for( int i=2;i<N;i++ )
{
if( visit[i] == 0)
{
prime.push_back(i);
for( int j=i*2; j<N; j=j+i )
{
visit[j] = 1;
}
}
}
}
void sol(long long n, vector<int>&prime)
{
ll ans = n;
for(int i=0; i<prime.size() || prime[i]>n; i++)
{
while(n%prime[i]==0)
{
n=n/prime[i];
ans = prime[i];
}
}
ans = max(ans, n);
cout<<ans<<endl;
}
int main()
{
ll tc, n;
sieve();
cin>>n;
sol(n, prime);
return 0;
} |
使用C ++中的递归来计算数字的最大质数。该代码的工作解释如下：
1
2
3
4
5
6
7
8
9
10
11
12
| int getLargestPrime(int number) {
int factor = number; // assumes that the largest prime factor is the number itself
for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
if (number % i == 0) { // checks if the current number(i) is a factor
factor = max(i, number / i); // stores the larger number among the factors
break; // breaks the loop on when a factor is found
}
}
if (factor == number) // base case of recursion
return number;
return getLargestPrime(factor); // recursively calls itself
} |
这是我在c＃中的尝试。最后打印出的数字是最大的素数。我检查了，它可以工作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| namespace Problem_Prime
{
class Program
{
static void Main(string[] args)
{
/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/
long x = 600851475143;
long y = 2;
while (y < x)
{
if (x % y == 0)
{
// y is a factor of x, but is it prime
if (IsPrime(y))
{
Console.WriteLine(y);
}
x /= y;
}
y++;
}
Console.WriteLine(y);
Console.ReadLine();
}
static bool IsPrime(long number)
{
//check for evenness
if (number % 2 == 0)
{
if (number == 2)
{
return true;
}
return false;
}
//don't need to check past the square root
long max = (long)Math.Sqrt(number);
for (int i = 3; i <= max; i += 2)
{
if ((number % i) == 0)
{
return false;
}
}
return true;
}
}
} |
这是我快速计算最大素数的方法。
基于这样的事实，修改后的x不包含非素数因子。为此，一旦找到一个因数，我们便将x除以。然后，剩下的唯一事情就是返回最大的因数。这已经是黄金了。
代码(Haskell)：
1
2
3
4
5
| f max' x i | i > x = max'
| x `rem` i == 0 = f i (x `div` i) i -- Divide x by its factor
| otherwise = f max' x (i + 1) -- Check for the next possible factor
g x = f 2 x 2 |
以下C ++算法不是最佳算法，但适用于十亿以下的数字，而且运算速度非常快
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
using namespace std;
// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
int i,count=0;
if(n==1 || n==2)
return true;
if(n%2==0)
return false;
for(i=1;i<=n;i++){
if(n%i==0)
count++;
}
if(count==2)
return true;
else
return false;
}
// ------ nextPrime -------
// Finds and returns the next prime number
int nextPrime(int prime){
bool a = false;
while (a == false){
prime++;
if (is_prime(prime))
a = true;
}
return prime;
}
// ----- M A I N ------
int main(){
int value = 13195;
int prime = 2;
bool done = false;
while (done == false){
if (value%prime == 0){
value = value/prime;
if (is_prime(value)){
done = true;
}
} else {
prime = nextPrime(prime);
}
}
cout <<"Largest prime factor:" << value << endl;
} |
通过" James Wang"在网络上找到了该解决方案
1
2
3
4
5
6
7
8
9
10
11
| public static int getLargestPrime( int number) {
if (number <= 1) return -1;
for (int i = number - 1; i > 1; i--) {
if (number % i == 0) {
number = i;
}
}
return number;
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
while n%i==0:
n=n/i
factors.add(i)
i+=1
factors.add(n)
largest=max(factors)
print factors
print largest |
在我看来，给出的算法的第2步将不会是一种非常有效的方法。您没有合理的期望，这是首要的。
同样，先前的答案暗示着Eratosthenes筛网是完全错误的。我刚刚编写了两个程序来分解因子123456789。一个基于Sieve，一个基于以下内容：
1
2
3
4
5
6
7
8
9
| 1) Test = 2
2) Current = Number to test
3) If Current Mod Test = 0 then
3a) Current = Current Div Test
3b) Largest = Test
3c) Goto 3.
4) Inc(Test)
5) If Current < Test goto 4
6) Return Largest |
这个版本比Sieve快90倍。
问题是，在现代处理器上，操作类型的重要性远远小于操作数量，更不用说上面的算法可以在缓存中运行，而Sieve不能。筛选器需要执行很多操作才能剔除所有合成数字。
另外，请注意，我在确定因素时将其分开会减少必须测试的空间。
首先计算一个存储质数的列表，例如2 3 5 7 11 13 ...
每次对素数进行因式分解时，请使用Triptych的实现，但要迭代此素数列表，而不是自然整数。
使用Java：
对于int值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public static int[] primeFactors(int value) {
int[] a = new int[31];
int i = 0, j;
int num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
int[] b = Arrays.copyOf(a, i);
return b;
} |
对于long值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| static long[] getFactors(long value) {
long[] a = new long[63];
int i = 0;
long num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
long j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
long[] b = Arrays.copyOf(a, i);
return b;
} |
这可能并不总是更快，但是对于找到一个主要的除数，我们会更加乐观：
N是您的电话号码
如果是素数，则return(N)
计算素数直到Sqrt(N)
按降序排列素数(从大到大)
-
如果N is divisible by Prime，则Return(Prime)
编辑：在第3步中，您可以使用Eratosthenes筛子或Atkins筛子或任何您喜欢的筛子，但是筛子本身不会找到最大的主要因素。 (这就是为什么我不选择SQLMenace的帖子作为正式答案的原因...)
我认为最好将所有可能小于n的素数存储在某个地方，然后遍历它们以找到最大的除数。您可以从prime-numbers.org获取质数。
我当然认为您的电话号码不是太大：)
不是最快的方法，但是可以！
1
2
3
4
5
6
7
8
9
10
| static bool IsPrime(long num)
{
long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
for (long i = 2; i <= checkUpTo; i++)
{
if (num % i == 0)
return false;
}
return true;
} |
这是与生成器相同的功能@行程单，也略有简化。
1
2
3
4
5
6
7
| def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1 |
然后可以使用以下公式找到最大质数：
1
2
| n= 373764623
max(primes(n)) |
以及使用以下方法发现的因素列表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>
factor(long int n)
{
long int i,j;
while(n>=4)
{
if(n%2==0) { n=n/2; i=2; }
else
{ i=3;
j=0;
while(j==0)
{
if(n%i==0)
{j=1;
n=n/i;
}
i=i+2;
}
i-=2;
}
}
return i;
}
void main()
{
clock_t start = clock();
long int n,sp;
clrscr();
printf("enter value of n");
scanf("%ld",&n);
sp=factor(n);
printf("largest prime factor is %ld",sp);
printf("Time elapsed: %f
", ((double)clock() - start) / CLOCKS_PER_SEC);
getch();
} |
