当前位置:首页 » Project Euler » 详细页

Squarefree Numbers 题号:193 难度: 55 中英对照

A positive integer n is called squarefree, if no square of a prime divides n, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.

How many squarefree numbers are there below 250?

Solution

# 193 由题意知满足条件的squarefree 数可以表示为: $$ n=p_1p_2\cdots p_k $$ 其中$p_1, p_2 \cdots ,p_k $ 表示$k$个**互不相同的素数**,$n$为这$k$个素数的乘积。 直观的想法,首先可以求出小于数$n$的素数的集合 $$ PRIMES = \begin{bmatrix} p_1 , p_2,\cdots ,p_m \end{bmatrix} $$ 在求解$PRIMES$ 集合时,使用[Prime Sieve 方法](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)(又叫做 Sieve of Eratosthenes)来求解素数的集合,这种方法的原理是从2开始,将每个素数的各个倍数,标记成合数。一个素数的各个倍数,是一个差为此素数本身的等差数列,此为这个筛法和试除法不同的关键之处,后者是以素数来测试每个待测数能否被整除,所以这样求解的效率更高。此求解素数方法在以后会经常用到,掌握它很有必要。 接下来统计$1\sim n$内满足条件的squarefree 数的个数,可以先求出不满足条件的non squarefree 数的个数,再用$n$减去non squarefree 数的个数,即为所求结果。 $1\sim n$ 中non squarefree 数是因子包含$PRIMES$ 集合中任一元素$p_k$的平方 $p_k^{2}$的数,因此我们可以借鉴Prime Sieve方法的思想,从$PRIMES$ 第一个元素平方开始遍历包含元素平方因子(以及其倍数)的数,统计他们的个数,得到non squarefree 数的个数,从而得到 squarefree 数的个数。 *引申:本题中的square free number与[Mobius Function](https://en.wikipedia.org/wiki/M%C3%B6bius_function) 有关,通过对Mobius Function 的了解后知道满足条件的square free 数的个数为:* $$ Q(x) \approx x\prod \limits_{p\ prime }(1-\frac{1}{p^{2}}) = \frac{6x}{\pi^{2}} + O(\sqrt x) $$ *以本题为例,准确结果为$684465067343069$,通过上式获得的结果只差$1485$.*

Code

public class p193 {
    private static long MAX;
    private static long[] PRIMES;


    public static void main(String[] args) {
        long start = System.nanoTime();
        long result = run();
        long end = System.nanoTime();
        System.out.println(result);
        System.out.println((end - start) / 1000000 + "ms");
}

    private static long run() {
        int N = 50;
        MAX = (long) Math.pow(2, N);
        // 获取所有小于sqrt(MAX)的质数
        PRIMES = getLongPrimes((int) Math.sqrt(MAX));
        long sum = MAX;
        // 将所有的包含Primes 平方因子的数全去掉,剩下的数就是square free
        for (int i = 0; i < PRIMES.length; i += 1) {
            sum -= countSquares(i, MAX);
        }
        return sum;

    }

    // 常用的获取小于数N的质数方法:PrimeSieve
    private static long[] getLongPrimes(int N) {
        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++) {
            isPrime[i] = true;
        }
        for (int i = 2; i * i <= N; i++) {
            if (isPrime[i]) {
                for (int j = i; i * j <= N; j++) {
                    isPrime[i * j] = false;
                }
            }
        }
        int primeCount = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i])
                primeCount++;
        }
        long[] primes = new long[primeCount];
        int k = 0;
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) {
                primes[k] = i;
                k++;
            }

        }
        return primes;
    }

    // 这里countSquare 方法的主要作用是在1~n中找出PRIMES[primeIndex] 的平方是其因子的数的个数,
    private static long countSquares(int primeIndex, long n) {
        long primeSquare = PRIMES[primeIndex] * PRIMES[primeIndex];
        long div = n / primeSquare;
        long temp = div;
        //  当primeindex >1时,排除含有0~primeindex-1 的PRIMES平方数因子的数的个数,避免重复计数
        if (div > 3 && primeIndex > 0) {
            long subCount = 0;
            for (int i = 0; i < primeIndex && (subCount = countSquares(i, temp)) > 0; i += 1) {
                div -= subCount;
            }
        }
        return div;
    }

}
684465067343069
763ms