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 ?

Crossed

Do you mean just getting rid of square numbers or are you trying to remove any number that has a square number as a factor too? Talking about "any repeated prime factors" implies the latter but the question itself implies the former. – Everlasting

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

Characharabanc

Could you tell us how to (efficiently) find all squares less n? – Publisher

@Ebe Isaac. for(int i = 1; i * i <= n; ++i) :) – Characharabanc

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

Shilohshim

Here's a method that can determine is a number is square free without factoring the number. The timing is dependent on how fast the sum of two squares can be calculated for a given number. math.stackexchange.com/questions/3064068/… – Nerti

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.

Venn

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.

Gamy

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.

Schoenfelder

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.

Deflagrate

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.

Cockatrice

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

Untune

Better than which one? I think you could try to explain what you mean a bit better. Maybe some formal approach, or example? – Hausfrau

Answer 9

Here is a naive Python implementation:

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

Voccola

Answer 10

As per @Armen's solution, we can use a modified form of the Sieve of Eratosthenes. Here is a C++ implementation, without the use of dynamic arrays:

    vector<unsigned> squarefree_eratosthenes(unsigned n) {
        unsigned count = n - 1;
        bool squarefree[n + 1];
        memset(squarefree, 1, sizeof(squarefree));
        for (int p = 2; p*p <= n; p++) {
            if (squarefree[p*p]) {
                for (int i = p*p; i <= n; i += p*p) {
                    count -= squarefree[i];
                    squarefree[i] = false;
                }
            }
        }
        vector<unsigned> sieved(count,0);
        count = 0;
        for (int p = 2; p <= n; p++) {
            if (squarefree[p]) {
                sieved[count] = p;
                count++;
            }
        }
        return sieved;
    }

Hedjaz