2012年5月18日星期五

GAP - Prime number

GAP support Primality Test和Factorization。

gap> IsPrime(4);IsPrime(5);
false
true

又例如:

gap> Factors(2^256+1);
[ 1238926361552897, 
  93461639715357977769163558199606896584051237541638188580280321 ]
gap> Factors(Factorial(20));
[ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 
  3, 5, 5, 5, 5, 7, 7, 11, 13, 17, 19 ]

很長吧,到底有多少個2呢!可以用Prime Power方式表示:

gap> PrimePowersInt(Factorial(20));
[ 2, 18, 3, 8, 5, 4, 7, 2, 11, 1, 13, 1, 17, 1, 19, 1 ]

這個list以[p1, e1, p2, e2....]來表示,pi是prime factor,ei是pi的exponent。除了Prime Power表達外,亦可以乘數表示,

gap> PrintFactorsInt(Factorial(20));
2^18*3^8*5^4*7^2*11*13*17*19

要找尋某數的下一個prime number或上一個,可以這樣,

gap> NextPrimeInt(10); PrevPrimeInt(20);
11
19

GAP本身內置頭百多個prime number,若想知Natural number中第二十個prime number是,

gap> Primes[20]; Size(Primes);
71
168

可惜只有頭一百六十八個,打後便要用NextPrimeInt,

gap> Primes[168]; NextPrimeInt(Primes[168]);
997
1009

另外,若想知某數以下的prime number數目,卻不見有這function,只要這樣,

gap> Size(Filtered([1..10000], IsPrime));
1229

沒有留言:

發佈留言