1樓:zball
現在的sota是general number field sieve.
很方便實現的快速演算法有lenstra's elliptic curve factorization和self initializing quadratic sieve.前面那個可以分解五六十位,後面那個常用來分解八十位以上的數。
2樓:九子蘭
對輸入任乙個大於1的數進行質因數分解,當輸入小於1的數時,退出。12位以內的任意數秒解,但超過12位時,卡了,解不出,沒反映,請教大神。
3樓:一粒沙子
#使用python進行正整數的因式分解
while True:
x=input('請輸入乙個大於0整數:')x=eval(x)
if x<=0 or x!=int(x):
print('你輸入的數字不合法')
else:
break
t=xresult存放因式
if x==1:
else:
i=2while True:
if t==i:
break
if t%i==0:
t=t/i
else:
i+=1
print(x,'=','*'.join(map(str,result)))#把列表的每乙個元素用*連線起來
4樓:Cubeneo
600851475143=71*839*1471*6857Pascal的解決方式
Varn : Int64 ; i : Longint ;
Begin
readln( n ) ;
if n<>1
then write( n , '=' )else write( n , '=1' );
i := 2 ;
while n<>1 do
Begin
if ( n mod i )=0then Beginn := n div iwrite( iif n<>1then write( '*'i := 2End
else inc( i ) ;
End;
writeln;
End.
5樓:洛島
deflargestPrime(n
):import
math
fori
inrange(2
,min
(math
.sqrt(n
)+1,
n)):ifn
%i==0
:return
max(
largestPrime(i
),largestPrime(n
/i))returnn
6樓:
我在尤拉計畫裡見過這道題,我當時的解題思路是這個數被2除如果能整除,這個數 = 這個數 \ 2,收集下這個除數如果不能整除 ,除數 = 除數 + 1
每次能被整除後,除數重新從2開始迴圈
直到這個數等於1的時候,在收集中的除數中找最大的那個數。
# -*- coding: utf-8 -*-"""The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
"""x = 600851475143
def funct(x):
divisor = 2
elsedivisor =divisor + 1return result
b = funct(x)
print (max(b))
當然這個思路是有改進空間的,因為乙個數不能被2整除,就必然不能被4,6,8,10……整除。
7樓:
Scala
deffindPrimeFactors(n:Long
,list
:List
[Long]=
List
()):
List
[Long]=
list
}val
answer
=findPrimeFactors
(600851475143L
)Python
import
math
defisPrime(n
):return
not[
iforiin
range(2
,int
(math
.sqrt(n
))+1)
ifn%i
==0]def
maxPrimeFactors(n
):x=[
iforiin
range(2
,int
(math
.sqrt(n
))+1)
ifisPrime(i
)andn%
i==0]
y=[n
/iforiinx
ifinotin
xand
isPrime(n
/i)]if
notsum([x
,y],):
return-1
else
:return
max(
sum([x,
y],))answer3
=maxPrimeFactors
(600851475143)
8樓:
Ruby程式如下:
def prime_factors n
return if n < 2
factors =
i = 2
while i <= n
while n % i == 0
n = n / i
factors << i
endi += 1
endfactors.uniq!
factorsend
9樓:楊勤榮
Pollard P進行素因子分解
據說當年這個叫Pollard因為考試的時候乙個簡單的因子分解的題算不出來(估計是求最大公因數之類的問題),名落孫山,結果後來發誓要搞乙個自己的分解演算法,於是發奮讀書,最終成為一代名家的。
10樓:
Common Lisp的版本
(defun largest-prime-factor (n)(labels ((rec (num acc)cond ((= 1 num) acc)
lt;= num 2) num)
t (let ((fac (do ((i 2 (1+ i)))or (>= i num)
zerop (mod num i))) i))))rec (/ num fac) fac))))))(rec n 1)))
(largest-prime-factor 600851475143)
11樓:依雲
Linux 下直接用 factor 程式:
$ factor 600851475143
600851475143: 71 839 1471 6857
12樓:Rio
Python 的解: def primefactors(n):
'''Generate all prime factors of n.'''
f = 2
while f * f <= n:
while not n % f:
yield f
n //= f
f += 1
if n > 1:
yield n print max(primefactors(600851475143))
為什麼大整數分解質因數很困難?
一葉孤城 如下所示,第一行間隔為1,數字依次為1 2 3 第二行間隔為2,數字依次為2 4 6 第三行間隔為3,數字依次為3 6 9 依次類推,這樣一直下去。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2 4 6 8 ...
大數的質因數分解為什麼會破解密碼?
viness RAS的加密原理大概是這樣的。先選擇兩個大的質數p和q,然後自然的有n p q,有了這個前提之後我們開始生成公鑰和秘鑰。1 公鑰的選取方式是這樣的 a.首先計算 這個東西是尤拉函式,大概的意思就是說比n小的正整數裡面和n互質的數有多少個 根據尤拉函式的性質有 上述公示成立的前提呢就是p...
如何用python實現SVD分解呢?
將陣列按第一行從大到小排序 order lambdaA A.T np.argsort A.T 0 T 補齊列空間的單位正交基 add null lambdaU np.row stack U T,scipy linalg null space U T T T defsvd A m,n A.shape ...