0
|
3987 Views
|
2 Replies
|
1 Total Likes
View groups...
Share
GROUPS:

# Creative way newbie shot himself in the foot?

Posted 9 years ago
 Please look at the following code (Yes, i try to solve a DLP :) - where i want to find out if a number is a product of some primes, taken from a list of the first (300) primes. Then Please explain me why 171! isn't smooth - all prime factors it contains are well below 171 and thus should be in SmallPrimes If you find the time, feel free to add some speedups and hints for better style. The code below is attached as notebook as well p = 1780119054785422665282375624501599901452321563691206742732744503144428 6578873702077061269525212346307956715678477846644997065077092072785705 0009668388144034129745221171818506047231150039301079959358067395348717 0663198022620197149665241350609459137075949565146728556906067941358375 42707371727429551343320695239 SmallPrimes = Table[Prime[i], {i, 1, 300}] PrimeQ[p] NumberOfPrimes = Length[SmallPrimes] RemoveFactor[n_, q_] := Block[{i = n}, While[Mod[i, q] == 0, i = i/q]; Return[i] ] RemoveFactor[144, 2] IsSmoothQ[n_] := Block[{t, i}, t = Mod[n, p]; For[i = 1, i <= NumberOfPrimes, i = i + 1, t = RemoveFactor[t, SmallPrimes[[i]]] ]; Return[t == 1]; ] IsSmoothQ[170!] (* gives True *) IsSmoothQ[171!] (* gives False *) Attachments:
2 Replies
Sort By:
Posted 9 years ago
 Here is a short variant. smallPrimes = Table[Prime[i], {i, 1, 300}]; smallPprod = Times @@ smallPrimes; smoothQ[n_] := FixedPoint[#/GCD[#, smallPprod] &, n] == 1 
Posted 9 years ago
 Ah - i got it. Remove the "t = Mod[n,p]" statement from IsSmoothQ. If breaks because 170!