查找数字的最大素数因子的算法
在计算机科学中，查找数字的最大素数因子的算法通常称为“素数因子分解”。以下是一个简单的算法，用于查找一个给定数字的最大素数因子：
- 首先，我们需要一个函数来检查一个数字是否为素数。素数是一个大于1的自然数，只能被1和它本身整除。我们可以编写一个名为
is_prime的函数来检查一个数字是否为素数：
def is_prime(n):
if n <= 1:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True- 接下来，我们需要一个函数来找到一个数字的最大素数因子。我们可以编写一个名为
largest_prime_factor的函数来实现这个功能：
def largest_prime_factor(n):
largest = 1
while n % 2 == 0:
largest = 2
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i == 0:
largest = i
n //= i
if n > 2:
largest = n
return largest- 最后，我们可以使用
largest_prime_factor函数来查找一个给定数字的最大素数因子。例如，如果我们想要找到数字123456789的最大素数因子，我们可以调用largest_prime_factor函数：
n = 123456789
largest = largest_prime_factor(n)
print(largest)这将输出数字123456789的最大素数因子，即123456789本身。
需要注意的是，这个算法并不是最高效的算法，但它足够简单，可以让您快速地找到一个数字的最大素数因子。在实际应用中，您可能需要使用更高效的算法，例如“Pollard's rho algorithm”或“AKS primality test”。
相关·内容
26回答
计算一个数的最大素因数的最佳方法是什么？ 我认为最有效的方法是： 找出整除的最小质数 检查除法结果是否为质数 如果不是，找到下一个最低的 转到2。 我把这个假设建立在更容易计算小素数因子的基础上。这是正确的吗？我还应该研究哪些其他方法？ 编辑:我现在已经意识到，如果有超过2个素数因子在起作用，我的方法是徒劳的，因为当结果是另外两个素数的乘积时，步骤2失败了，因此需要一个递归算法。 再次编辑:现在我意识到这仍然有效，因为最后找到的质数必须是最高的，因此对步骤2的非质数结果的任何进一步测试都将导致较小的质数。
浏览 361提问于2008-08-22得票数 194
回答已采纳
1回答
我在topcoder上发现了euler的phi函数的一个实现。守则如下：
int fi(int n) {
int result = n;
for(int i=2;i*i <= n;i++) {
if (n % i == 0) result -= result / i;
while (n % i == 0) n /= i;
}
if (n > 1) result -= result / n
浏览 2提问于2016-11-28得票数 2
回答已采纳
向我提出的问题是：
“数字600851475143的最大素因子是什么?"
这个程序是用来找出答案的，完全是这样的，使用C：
#include<math.h> // for remainder because % does not work with double or floats
#include<stdio.h>
main()
{
double x=600851475143,y=3.0;
while(x!=y) // divide until only the number can divi
浏览 2提问于2013-05-14得票数 1
1回答
给定n，我希望找到这样的phi(i) = n。n <= 100,000,000。i = 202918035 for n = 99683840的最大值。我想要解决
我的方法是预先计算所有数字的整体函数，直到最大i。为此，我首先使用erathronese的筛子找到直到最大i的所有质数。素数的总数是在筛选时记录的。然后使用
然后我在phi数组中搜索输入的数字，并将结果打印出来。但它超出了时间限制。什么可以在预计算中进一步优化，或者有更好的方法来做到这一点？
我的代码是：
#include <stdio.h>
#include <stdlib.h>
#inclu
浏览 0提问于2013-01-27得票数 5
回答已采纳
这是我的第一个问题。
我一直在解决eulerproject.net问题，在为给定的输入获得正确答案之后，我想尝试不同的输入，以检查我的代码是否正常工作。好像没有。
最大的素因子应该是1137193159，但是我得到了79。当然，因为我在这里设置了上限。但是，如果我将上限提高一点，我的代码就会变得非常慢。
这是我用来找出最大素因子的函数。
def largest_prime_factor(n) :
upper_limit = math.trunc((n**0.5))
while(1) :
for num in range(upper_limit, 2, -1) :
浏览 3提问于2020-05-31得票数 1
回答已采纳
我想要做一个程序，可以比较大小为100^100的数的素因式分解。我想让程序告诉我是否有2，例如，在素数分解中，但是我不想知道有多少.比我想要比较两个数字的素因式分解..。有人能帮忙吗？困难在于数字的大小..。以及程序的效率..。我想比较两个数字只需要10秒.
我有这个；
import java.util.ArrayList;
import java.util.List;
public class PrimeFactorisation {
public static List<Integer> primeFactors(int numbers) {
浏览 4提问于2016-10-08得票数 1
回答已采纳
3回答
创建大量数字的库或方法
、、、
我正在研究一种素因式分解算法。为了测试它，我需要一些大的数字，很少和大素数。例如，Number=(BigPrime1*BigPrime2)。
所谓Large Number，我的意思是，与当前的RSA算法用于密钥代时一样大。
我怎样才能找到其中的一些数字来测试和挑战我的算法。
他们有图书馆吗？或者任何网站已经有一些挑战的数字？
浏览 0提问于2013-08-04得票数 0
回答已采纳
3回答
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
我看到了上面Euler phi函数的实现，它是O(sqrt ).I没
浏览 8提问于2015-06-05得票数 3
回答已采纳
1回答
除数算法
、、、
我得到了一个整数列表(最多1000个整数)，这些整数乘以给定的整数n。
我需要在整数n的所有因子中找到最高的幂。
例如: 4,7,8乘以224，然后最高功率将是5，自224=2^2*7*2^3=2^5*7以来。
问题是，1000个整数可以高达2^64，因此n非常大。
解决这个问题的伟大算法是什么？
浏览 5提问于2016-10-30得票数 1
回答已采纳
1回答
isPrime::Integer->Bool
isPrime n=not (hasfactor n 2(div n 2))
hasfactor::Integer->Integer->Integer->Bool
hasfactor n low high
|low>high=False
|mod n low==0=True
|otherwise = hasfactor n (low+1) high
我理解大部分代码，除了第二行，not (hasfactor n 2(div n 2))。为什么更高的界限是(div n 2)？假设我们使用test
浏览 1提问于2017-04-23得票数 0
2回答
求因子总和
、、、
为什么这段代码返回一个数字的因子之和？
在几个Project Euler问题中，要求您计算因子和作为问题的一部分。在那里的一个论坛上，有人发布了以下Java代码作为求和的最佳方法，因为您实际上不必找到单个因子，只需找到质数(您不需要了解Java，您可以跳到下面的摘要)：
public int sumOfDivisors(int n)
{
int prod=1;
for(int k=2;k*k<=n;k++){
int p=1;
while(n%k==0){
p=p*k+1;
n/=k;
浏览 0提问于2010-12-17得票数 8
回答已采纳
对于射影器，找不到600851475143的素数。我的代码成功地计算了测试编号13195的最大素数因子和我抛给它的每个测试数，但不知怎么的，它随着大素数而退化。你知道为什么吗？
#include <iostream>
#include <queue>
using namespace std;
int split(int split);
int largestprimefactor(priority_queue<int> myints);
int main()
{
int response = 2;
do{
priority_queue&
浏览 3提问于2013-12-23得票数 1
回答已采纳
1回答
我试图从Euler项目中解决一个问题: 13195的素因子是5，7，13和29。数字600851475143中最大的素因子是什么？以下是我的尝试：
def getPrimeNumbers(testNumber):
'''
For a given number it returns a list of all prime numbers from 2 to given number.
>>> getPrimeNumbers(15)
[2,3,5,7,11,13]
'''
浏览 0提问于2020-01-07得票数 -4
回答已采纳
我在做一个小项目。我的任务是在数组中查找与所有其他值互质的元素。我想出了一个使用双for循环的方法。然而，我认为时间复杂度不会是有利的，特别是如果元素数组很大的话。
这就是我所拥有的：
ArrayList<Integer> getAllCoPrimes(int[] inputs) {
ArrayList<Integer> coprimes = new ArrayList<>();
int[] elementsCount = new int[inputs.length];
for (int i = 0; i < inputs.le
浏览 0提问于2020-10-19得票数 0
3回答
我一直在做一些Project问题来学习/实践Lua，而我最初寻找n最大素因子的快速和肮脏的方法非常糟糕，所以我查找了一些代码来查看其他代码是如何做到的(试图理解不同的分解方法)。
我遇到了以下情况(最初使用Python --这是我的Lua)：
function Main()
local n = 102
local i = 2
while i^2 < n do
while n%i==0 do n = n / i end
i = i+1
end
print(n)
end
这一因素在非常短的时间内产生了巨大的数字--几乎是
浏览 5提问于2015-07-27得票数 2
回答已采纳
我必须找到除以所有数组元素的最小整数数(其中每个这样的integer>=2)。例如，如果数组为[2,4,6,8,10]，则答案为1(因为2除以所有数组元素)。另一个例子，如果数组是[2,3,4,9]，那么答案是2(因为我们至少需要2个不同的数字，2和3，满足条件)。
我决定生成给定数组的所有子数组，存储在2D数组中，然后按大小降序对所有子数组进行排序。然后迭代二维数组，一旦找到除以子数组所有元素的数字，就返回该子数组的索引+1。
因此，对于上面的第一个示例，要检查的第一个子数组将是主数组本身(在排序后)，并且将找到一个数字(2)来划分其所有元素。因此，返回值将为index+1=0+1=1
浏览 0提问于2020-10-02得票数 0
3回答
我正在编写一个代码，以找到一个非常大的数字中最大的素因子。
欧拉计划的问题3: 600851475143这个数字最大的素因子是什么？
我在C...but中编写了它，数据类型long long int不足以容纳这个值。
现在，我用Python重写了代码。如何减少执行所需的时间(因为这需要相当长的时间)？
def isprime(b):
x=2
while x<=b/2:
if(b%x)==0:
return 0
x+=1
return 1
def lpf(a):
x=2
i=2
浏览 5提问于2013-08-29得票数 1
回答已采纳
我试着通过这个代码找出任何给定数字的质因数。这段代码对于较小的数字工作得很好，但对于较大的数字(如12345678)，程序不会终止。怎么了？?
using namespace std;
bool isPrime(int i)
{
for(int k=2;k<i;k++)
{
if(i%k==0)
{
return false;
}
}
if(i==1)
{
return false;
}
return true;
}
int main()
{
浏览 11提问于2020-11-16得票数 0
1回答
问题
一个带有Biginteger计算冻结的控制台应用程序
详细信息
我正在用C#开发一个控制台应用程序，它测试非常大的数字(10到几十到数百)是否是素数。由于默认整数类型只能处理最多10^19 (long，ulong)的数字，所以我使用的是BitInteger类。但是，当我在Visual中以调试模式运行应用程序时，应用程序会冻结。
static void Main(string[] args)
{
int exp = 100;
var bi = BigInteger.Pow(10, exp);
var sw = new Stop
浏览 5提问于2017-11-25得票数 1
回答已采纳
我正在编写一个Java程序，它计算一个大数中最大的素数因子。但是我对程序的复杂性有一个问题，我不知道是什么原因导致这个程序永远运行大量的数字，它对小的数字很好。
我的发言如下：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
public class Largest_prime_factor {
public static void main(String[] args)
{
//ArrayList primesArray = new ArrayList();
浏览 3提问于2016-10-04得票数 3
回答已采纳
假设我有一个很大的数字$n$ = $pq$，其中$p$和$q$是素数。
一个新的数字$n'$是通过增加这些素因子而产生的。我怎样才能找到这个新数字的主要因素呢？
浏览 0提问于2018-04-17得票数 0
给定一个数字n，编写一个程序来找到从n开始的九个连续数中每一个最大素数的和。
我可以得到因子，但是对于每个值，如果有多个因子是素数，我只想得到那些我无法得到的素因子中的最大值。
def find_g(num):
factor=[]
list1=[]
list2=[]
for i in range(0,num-1):
factor.append(num+i)
print(factor)
for f in factor:
for i in range(2,f+1):
if(f%i==0 and
浏览 1提问于2019-06-27得票数 1
回答已采纳
3回答
我已经开始做在Project上找到的问题，并且刚刚解决了问题3。然而，我觉得我的代码很长，而且太暴力了。我希望有人能看一看，给我一些关于这个问题和未来编程的指导方针。这将帮助我清理它，甚至只是揭示更好的方法解决这个问题。
问题3指出：
13195的素因子为5、7、13和29。数字600851475143中最大的素因子是什么？
int primeFactor = 0;
int pfCounter = 0;
int[] pf = new int [1229];
int[] numbers = new int[10000];
long number = 600851475143L;
int p =
浏览 0提问于2013-03-20得票数 2
回答已采纳
这是一个(相当糟糕的)项目Euler问题的解决方案。问题是要找到10_001st素数。下面的代码可以做到这一点，但它需要8分钟才能运行。你能解释一下为什么会出现这种情况吗?如何优化它？
primes = []
number = 2.0
until primes[10000] != nil
if (2..(number - 1)).any? do |n|
number % n == 0
end == false
primes << number
end
number = number + 1.0
end
puts primes[10000]
浏览 0提问于2013-03-18得票数 1
回答已采纳
假设你有10e4个数字。每个数字不超过10e6。如果每个数字可以表示为两个素数的倍数，那么如何有效地检查每个数字？ 例如: 15可以表示为3 *5.6。6可以表示为2*3。但8不能由两个素数表示。
浏览 54提问于2021-09-28得票数 0
1回答
我试图在一个交互式网站上解决一个问题，在用我的一些例子尝试了代码后，它似乎可以工作，但是，如果我在网站上加载它，它会说有一个错误的答案，这让我认为有一个(或多个)情况下我的代码无法正确执行，但我似乎找不到这样的情况。
问题是：
对于每个给定的整数，按升序返回它的素因子。输入的第一行(自然数)是我们想要检查的数字的数量。下面几行是大于2的数。对于每一个数(在一行中)，以升序返回该数、一个分号及其素除数。每个除数只能出现一次。
示例：
2
12
1024
应该返回
12: 2 3
1024: 2
我的C++代码：
#include <iostream>
using namesp
浏览 0提问于2020-03-27得票数 3
RSA模是N = pq，其中p和q是素数。我从某个地方读到，随着密钥长度的增加，解密RSA加密所需的时间呈指数增长，这取决于N的值，而后者又取决于p和q。有任何数学证据来解释这一现象吗？
浏览 0提问于2019-06-14得票数 0
这是我在离散数学中的作业。我试着这样做。
procedure prime_numbers (x)
n:= 1
for i:= to n<=x do
n mod i=1 then
return (prime)
end prime_number.
浏览 0提问于2010-08-19得票数 1
2回答
我为Euler项目的第二个问题编写了以下程序："Project #3:最大素因子“.It应该打印出所提供输入的所有最高素数因子。
import java.util.Scanner;
public class euler_2 {
public static boolean isPrime(int n) {
if (n % 2 == 0) return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0)
return f
浏览 2提问于2016-05-31得票数 0
回答已采纳
5回答
我正在尝试编写一个程序来寻找一个非常大的数的最大素因数，并且已经尝试了几种方法，但都取得了不同的成功。到目前为止，我找到的所有工具都慢得令人难以置信。我有一个想法，我想知道这是不是一个有效的方法：
long number = input;
while(notPrime(number))
{
number = number / getLowestDivisiblePrimeNumber();
}
return number;
此方法将接受一个输入，并将执行以下操作：
200 -> 100 -> 50 -> 25 -> 5(返回)
90 -> 45 -&g
浏览 0提问于2009-12-10得票数 7
回答已采纳
2回答
这是这个问题的后续问题：
以下是一位大师对这个问题的解决方案：
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const int MAXN = 100100;
const int MAXP = 10001000;
int p[MAXP];
void init() {
for (int i = 2; i < MAXP; ++i) {
if (p[i] == 0) {
for (in
浏览 0提问于2012-09-11得票数 0
回答已采纳
1回答
我需要做一个打印所有质数的程序，下面是我所做的：
#include <stdio.h>
int main(void) {
long long t,m,n,i,i2,i3,found;
float p;
scanf ("%lld" , &t);
for (i=1;i<=t;i++) {
scanf ("%lld%lld" , &m ,&n);
for (i2=m;i2<=n;i2++) {
found=0;
浏览 1提问于2014-03-23得票数 0
给出了一个1-indexed数组--大小为N的，由<code>E 112</code>x>E 213</代码>给出了该数组i<代码>E29</code>的任意2指数与<代码>E 110</code>j</code>E 211</code>E 211</code>之间的距离。现在，根据这些信息，我需要为每个索引i (1≤i≤N)找到索引j，以便1≤j≤N、i≠j<code>E 223</code>和<code>E 124</cod
浏览 9提问于2016-11-19得票数 0
回答已采纳
计算x！可能会非常昂贵，而且可能经常导致溢出。有没有办法找出x！如果没有计算x，是否可以被y整除？
对于y< x，它是平凡的；
但是，对于y> x，例如x =5和y=60，我很难找到一种不用计算x的方法！
浏览 8提问于2014-04-28得票数 4
回答已采纳
这是我的Fraction类代码
class Fraction:
"""Class for performing fraction arithmetic.
Each Fraction has two attributes: a numerator, n and a deconominator, d.
Both must be integer and the deonominator cannot be zero.
"""
def __init__(self,n,d):
""&#
浏览 1提问于2017-05-16得票数 1
3回答
Python素数
、、
我刚开始学习python。我在试着写一个打印素数no的程序。但它也打印了no。以5结尾。
n = 2
while n >= 2:
if n == 2:
print(n)
n += 1
while n >= 3:
if n == 3:
print(n)
n += 2
for i in range (3,n):
if n % i != 0:
print(n)
n +=
浏览 32提问于2018-01-01得票数 0
我读过一些关于数域筛的论文，但是我不知道这个算法在灌木丛中有什么帮助，甚至不知道数字字段是什么意思。这是什么？什么是因式分解？
我对这个话题很陌生，需要对上面的问题做一个简单的描述.
浏览 0提问于2016-05-25得票数 6
在一个数组中找到仅有的两个数字，其中一个除以另一个，即除法运算的结果是一个整数
Input Arrays Output
5 9 2 8 8/2 = 4
9 4 7 3 9/3 = 3
3 8 6 5 6/3 = 2
具有嵌套循环的暴力方法具有O(n^2)的时间复杂性。有没有时间复杂度更低的更好的方法？
这个问题是的一部分。
浏览 2提问于2018-01-31得票数 7
1回答
check x = filter((==0) . (\(x,y) -> x `mod` y)) $ zip (replicate 20 x) [1..20]
main = do
print $ take 1 $ filter ((==20) . length) [check x | x <- [1..]]
我试图通过http://www.compileonline.com/compile_haskell_online.php运行上面的代码，但随着评估数量的增加，它似乎使用了太多的资源，所以我可以搜索filter(==18)，但不能搜索filter(>=19)。有没有
浏览 2提问于2014-05-09得票数 0
解决方案：
事实证明，代码本身(可能)“没有什么问题”；它只是效率低下。如果我的数学是正确的，如果我继续运行它，它将在2011年10月14日星期五完成。我会告诉你的！
警告：--如果您试图解决Project #3，它可能包含扰流器。
问题是：
13195的素因子为5、7、13和29。
数字600851475143中最大的素因子是什么？
这是我试图解决的问题。我只是从Java和一般编程开始，我知道这不是最好或最有效的解决方案。
import java.util.ArrayList;
public class Improved {
public static void m
浏览 9提问于2011-02-18得票数 1
如何编写一个函数，返回除1以外的两个整数的所有公共除数列表。
x =
y =
L = []
for n in range(min(x,y)1):
if x%n == y%n == 0:
L.append(n)
print(L)
浏览 2提问于2022-01-03得票数 -3
4回答
优化素数分解算法
、、
下面是一个算法，它可以找到给定数字N的素数分解。我想知道是否有任何方法可以使用大数字来加快这一过程。我说的是20-35位数字。我想试着让它们尽可能快地运行。有什么想法吗？
import time
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
divisor = 2
while n > 1:
while n % diviso
浏览 0提问于2014-04-03得票数 1
这是Project问题#5，这个语句找到了第一个n个自然数最不常见的倍数。例如，1，2的最不常见倍数。10是2520。
我承认我只是在尝试一些随机的东西，我没想到下面这些东西会起作用(用Python编写)：
factors = int(input())
factorList = []
for i in range(2, factors+1):
factorList.append(i)
for i in range(len(factorList)-1):
for j in range(2*i+2, len(factorList), i+2):
fact
浏览 0提问于2016-09-22得票数 -2
4回答
我被要求将数组中每个数字的1以外的因子和数字本身相加。问题是它必须能够处理具有非常大数字的非常大的数组，而我目前的实现对于大小为100,000,000的数组需要很长的时间。我计算每个数字因子的代码是
static long countFactors(long num){
long count=0;
long max =(long) Math.floor(Math.sqrt(num));
for(int i=2; i<=max;i++){
if(num%i==0&&(i*i)!=num){
// count i
浏览 2提问于2013-09-16得票数 3
1回答
什么是最简单、最有效的逻辑来表达n！作为素数的力量的乘积？
我更感兴趣的是找到素数的幂，这样我才能知道因子的数目。就像n！可以用p1^e1 * p2^e2 ** pk^ek表示，其中每个p都是素数，那么n的因子数是(e1 + 1)(e2 + 1) . *(ek + 1)
浏览 4提问于2012-05-19得票数 3
回答已采纳
1回答
我试图解决项目Euler问题#3问题，它要求：
13195的素因子为5、7、13和29。数字600851475143中最大的素因子是什么？
您能检查一下代码并提出改进建议吗？
namespace FullPractice
{
public class PrimeFactorFinder
{
private readonly HashSet<int> _myPrimeFactors = new HashSet<int>();
private long _myNumber;
public void PrimeFactors(long num
浏览 0提问于2014-10-04得票数 1
3回答
我试图解决这个问题："2520是最小的数，可以除以1到10的每一个数，没有任何余数。
哪一个最小的正数可以被从1到20的所有数字平除？“
请不要告诉我答案，我真的很想自己解决它。我所需要的只是关于这个问题的数学方面的建议。因为这个过程太慢了，所以每个周期都增加一个并不是个好主意。还是存在变量类型不长的问题？
我试着得到在(1到10)之间，甚至(1和17)之间的所有数都可以被整除的数字，这个算法工作得很好。
int in_num = 1;
int score = 0;
public void calculate() {
while (true) {
score =
浏览 1提问于2019-08-17得票数 2
回答已采纳
1回答
我们有一组正整数。
我们通过计算这个集合中所有可能的整数对的最大公因子来创建一个新集。
我们重新执行上述步骤，直到只有一个成员留在集合中。
是否有一个O(n)方法来计算这个过程创建了多少个新集，以及最后一组中的成员是否为1？
一些python代码演示了我描述的过程。
from itertools import combinations
from fractions import gcd
import random
def gen_new_set(a):
count = 0
while len(a) != 0:
print str(count)+':\t&
浏览 2提问于2014-12-06得票数 0
回答已采纳
出于测试目的，我需要找到两个64位整数值，这两个值与具有特定位模式的128位中间值完全相乘。显然，我可以生成所需的中间值并除以随机值，直到我找到一个有效的组合，但是有没有更有效的方法呢？
浏览 7提问于2009-09-16得票数 3
回答已采纳
4回答
给定N个整数的固定数组A，其中N<=100,000和数组的所有元素也小于或等于100,000。A中的数字不是单调增加的，也不是连续的，也不是很方便地组织起来的。
现在，我被给予多达100,000个形式的查询{ V，L，R}，在每个查询中，我需要在范围L，R中找到与i一起的最大数Ai，它与给定的值V不是对等的(即GCD(V，Ai)不等于1)。
如果这是不可能的，那么也说明在给定范围内的所有数字都与V是相互作用的。
一种基本的方法是从L和R之间的每个Ai迭代，然后用V值计算GCD，从而找到最大值。但是，如果查询的数量也可以达到100,000，那么是否有更好的方法来做到这一点呢？在这种情况下，
浏览 1提问于2014-03-12得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
