Getting a list of square-free numbers

Question

One way to get that is for the natural 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 ?

Answer 1

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...

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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)).

Answer 9

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