[HP35s] Program for prime number (Wheel Sieve and Miller-Rabin)
|
02-15-2019, 03:07 PM
(This post was last modified: 02-15-2019 05:51 PM by Albert Chan.)
Post: #20
|
|||
|
|||
RE: [HP35s] Program for prime number (brut force)
(02-14-2019 01:10 PM)fred_76 Wrote: Version 3 Run time Curious about performance of checks vs. size of N Redo above tables, with cases checked = 4 + 8 * ceil((√(N) - 7)/30) Code: Digits Time(sec) Checks Speed(msec per check) It seems check speed unaffected by size of N. Timings depends mainly on number of checks required. It is possible to reduce required checks, by few applications of Fermat's method. Example, N = 999,999,999,989. Tried to complete the squares: Code: X Y^2 = X^2-N If Y is integer, above can be factored as (X + Y)(X - Y) None of above Y's worked, but it reduce cases checked greatly. (BTW, only the Y^2 ends in 36 need checking, others will never be integer square) Max factors to search = floor(next(X) - next(Y)) = floor((1e6 + 10) - √(20e6 + 19 + 92)) = 995537 -> Cases to check = 4 + 8 * ceil((995537 - 7) / 30) = 4 + 8 * 33185 = 265484 -> Removed checks = 266676 - 265484 = 1192 (or, 1192/8 = 149 turns) |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)