Article 6GFGK Factored random numbers

Factored random numbers

by
John
from John D. Cook on (#6GFGK)

A couple days ago Michael Nielsen posted an image of a one-page paper that gives an algorithm for generating factored random numbers, uniformly distributed from 1 to some designated N.

The algorithm does not generate random numbers then factor them. It's more efficient than that, generating the factorization along with the final result. It does require testing for whether a number is prime, but this is more efficient than factorization.

I thought about trying to code up the algorithm in Python, but then I see that @iconjack beat me to it.

from sympy import isprimefrom random import random, randintdef randfacts(N): while True: n, r, s = N, 1, [] while n > 1: if r > N: break if isprime(n := randint(1,n)): r *= n s.append(n) else: if random() The post Factored random numbers first appeared on John D. Cook.
External Content
Source RSS or Atom Feed
Feed Location http://feeds.feedburner.com/TheEndeavour?format=xml
Feed Title John D. Cook
Feed Link https://www.johndcook.com/blog
Reply 0 comments