Getting a list of square-free numbers
One way to get that is for the natu开发者_如何学Goral numbers (1,..,n) we factorise each and see if they have any repeated prime factors, but that would take a lot of time for large n. So is there any better way to get the square-free numbers from 1,..,n ?
You could use Eratosthenes Sieve's modified version:
Take a bool array 1..n;
Precalc all squares that are less than n; that's O(sqrt(N));
For each square and its multiples make the bool array entry false...
From http://mathworld.wolfram.com/Squarefree.html
There is no known polynomial time algorithm for recognizing squarefree integers or for computing the squarefree part of an integer. In fact, this problem may be no easier than the general problem of integer factorization (obviously, if an integer can be factored completely, is squarefree iff it contains no duplicated factors). This problem is an important unsolved problem in number theory because computing the ring of integers of an algebraic number field is reducible to computing the squarefree part of an integer (Lenstra 1992, Pohst and Zassenhaus 1997).
The most direct thing that comes to mind is to list the primes up to n and select at most one of each. That's not easy for large n (e.g. here's one algorithm), but I'm not sure this problem is either.
One way to do it is to use a sieve, similar to Eratosthenes'.
@Will_Ness wrote a "quick" prime sieve as follows in Python.
from itertools import count
# ideone.com/
def postponed_sieve(): # postponed sieve, by Will Ness
yield 2; yield 3; yield 5; yield 7; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe 2002
ps = postponed_sieve() # a separate base Primes Supply:
p = next(ps) and next(ps) # (3) a Prime to add to dict
q = p*p # (9) its sQuare
for c in count(9,2): # the Candidate
if c in sieve: # c's a multiple of some base prime
s = sieve.pop(c) # i.e. a composite ; or
elif c < q:
yield c # a prime
continue
else: # (c==q): # or the next base prime's square:
s=count(q+2*p,2*p) # (9+6, by 6 : 15,21,27,33,...)
p=next(ps) # (5)
q=p*p # (25)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s # original test entry: ideone.com/WFv4f
With a little effort, this can be used to pop out square-free integers, using the postponed_sieve() to serve as a basis for sieving by as few squares as possible:
def squarefree(): # modified sieve of Will Ness
yield 1; yield 2; yield 3; # original code David Eppstein,
sieve = {} # Alex Martelli, ActiveState Recipe 2002
ps = postponed_sieve() # a base Primes Supply:
p = next(ps) # (2)
q = p*p # (4)
for c in count(4): # the Candidate
if c in sieve: # c's a multiple of some base square
s = sieve.pop(c) # i.e. not square-free ; or
elif c < q:
yield c # square-free
continue
else: # (c==q): # or the next base prime's square:
s=count(2*q,q) # (4+4, by 4 : 8,12,16,20...)
p=next(ps) # (3)
q=p*p # (9)
for m in s: # the next multiple
if m not in sieve: # no duplicates
break
sieve[m] = s
It's pretty quick, kicking out the first million in about .8s on my laptop.
Unsurprisingly, this shows that this is effectively the same problem as sieving primes, but with much greater density.
You should probably look into the sieve of Atkin. Of course this eliminates all non-primes (not just perfect squares) so it might be more work than you need.
Googling a little bit I've found this page where a J program is explained. A part from the complex syntax, the algorithm allows to check whether a number is square-free or not:
generate a list of perfect square PS,
take your number N and divide it by the numbers in the list PS
- if there is only 1 whole number in the list, then N is square-free
You could implement the algorithm in your preferred language and iterate it on any number from 1 to n.
http://www.marmet.org/louis/sqfgap/
Check out the section "Basic algorithm: the sieve of Eratosthenes", which is what Armen suggested. The next section is "Improvements of the algorithm".
Also, FWIW, the Moebius function and square-free numbers are related.
I have found a better algorithm to calculate how many square-free numbers in a interval such as [n,m]. We can get prime that less than sqrt(m)
, then we should minus the multiples of those prime's square, then plus the multiples of each two primes' product less than m, then minus tree ,then plus four.... at the last we will get the answer. Certainly it runs in O(sqrt(m))
.
import math
def squarefree(n):
t=round(math.sqrt(n))
if n<2:
return True
if t*t==n:
return False
if t<=2:
return True
for i in range(2,t):
if n%(i*i)==0:
return False
else:
return True
精彩评论