[C/C++] BOJ #1016 Square Nono Number

Problem Description:

You are given two integers, min and max, which define a range of numbers [min, max]. Your task is to find how many numbers within this range are not divisible by the square of any integer greater than 1. Such numbers are called “non-square-free” numbers.

In mathematical terms, a number x in the range [min, max] is considered not square-free if there exists an integer k > 1 such that \(k^2\) divides x. Conversely, your task is to count how many numbers in the range [min, max] are square-free, meaning they are not divisible by any \(k^2\), where k > 1.

Input:
• Two integers min and max (\(1 \leq min \leq max \leq 10^{12}\)).
• The difference (max - min) will not exceed 1,000,000.

Output:
• Print the number of square-free numbers in the range [min, max].

 

This problem requires efficient algorithms because the range is very large, and a direct approach would not work within the given constraints. Efficient methods typically involve using a sieve-like algorithm to mark multiples of squares of integers starting from \(2^2\) within the given range.

 

This problem involves finding numbers that are divisible by square numbers greater than 1. You can think of it as an extended version of the Sieve of Eratosthenes.

Although the range of numbers is small, the numbers themselves are quite large, requiring us to compute a significant number of primes. To determine whether a number n is a prime, it can be done with a complexity of \(O(\sqrt{n})\).  Therefore, even though the numbers can go up to the order of \(10^{12}\), because we are dealing with square numbers, the primes we actually need to compute are on the order of \(10^6\).

In terms of computation, this is achievable in less than half the time limit. However, the success rate for solving this problem is very low, at just 18%.

 

Since the range is given as (min, max), constructing the Sieve of Eratosthenes requires introducing the concept of an offset. Naturally, min becomes the base offset. After determining a prime p, I used the remainder when dividing min by \(p^2\) as the offset.

For the case of p = 2, handling it separately allows us to focus only on odd numbers when performing the prime checks.

 

Squre Nono Numbers

Below is the code I wrote for this problem. Please consider it for reference only.

//----------------------------------------------------------
//    baekjoon #1016 - Square Free Number
//        - by Aubrey Choi
//        - created at 2019-06-14
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

static char check[1000001];
void mark(long long p, long long r, int n)
{
    for(long long i = (p - r)%p; i < n; i += p) check[i] = 1;
}
int main()
{
    long long min, max, r;
    int k, n, c = 0;
    scanf("%lld%lld", &min, &max);
    k = (int)sqrt(max);
    r = min % 4;
    n = (int)(max - min + 1);
    mark(4, r, n);
    for(long long p = 3; p <= k; p += 2)
    {
        r = min % (p*p);
        mark(p*p, r, n);
    }
    for(int i = 0; i < n; i++) if(check[i] == 0) c++;
    printf("%d\n", c);
}