Message Boards Message Boards

0
|
4575 Views
|
2 Replies
|
1 Total Likes
View groups...
Share
Share this post:

Creative way newbie shot himself in the foot?

Posted 10 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

  1. Please explain me why 171! isn't smooth - all prime factors it contains are well below 171 and thus should be in SmallPrimes
  2. 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:
POSTED BY: Thomas Vogler
2 Replies

Here is a short variant.

smallPrimes = Table[Prime[i], {i, 1, 300}];
smallPprod = Times @@ smallPrimes;

smoothQ[n_] := FixedPoint[#/GCD[#, smallPprod] &, n] == 1
POSTED BY: Daniel Lichtblau

Ah - i got it. Remove the "t = Mod[n,p]" statement from IsSmoothQ. If breaks because 170!<p<171! So only my second question remains open: Some hints for better style / faster code?

POSTED BY: Thomas Vogler
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract