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:
