Submission #41054350

---

Source Code Expand

/* InTheBloom_Template v1.04 (BETA) Last updated: 2023/4/25 */
/* Repository: https://github.com/InTheBloom/InTheBloom_Library */

/* Originally includes 'in_out.c', 'debug.c' */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

#define EPRINT_INT(x) {\
    long long Z = x;\
    fprintf(stderr, "Line %d: %s = %lld\n", __LINE__, #x, Z);\
}
#define EPRINT_STR(x) {\
    fprintf(stderr, "Line %d: %s = %s\n", __LINE__, #x, x);\
}
#define EPRINT_INT_ARRAY(x, n) do {\
    if (n > 0) {\
        fprintf(stderr, "Line %d: %s = [", __LINE__, #x);\
        for (int qq = 0; qq < n - 1; qq++) {\
            long long Z = x[qq];\
            fprintf(stderr, "%lld, ", Z);\
        }\
    long long Z = x[n - 1];\
    fprintf(stderr, "%lld]\n", Z);\
    } else {\
        fprintf(stderr, "[]\n");\
    }\
} while (0)

#define NEWLINE fprintf(stderr, "\n")

int read_int (void) {
    int x;
    scanf("%d", &x);
    return x;
}

double read_double (void) {
    double x;
    scanf("%lf", &x);
    return x;
}

long long read_long_long (void) {
    long long x;
    scanf("%lld", &x);
    return x;
}

void read_str (char *x) {
    scanf("%s", x);
}

void read_int_array (int *x, int n) {
    for (int i = 0; i < n; i++) {
        scanf("%d", &x[i]);
    }
}

void read_long_long_array (long long *x, int n) {
    for (int i = 0; i < n; i++) {
        scanf("%lld", &x[i]);
    }
}

// Defined with macros to support multiple types.

#define print_int_array_with_space(x, n) do {\
    for (int i = 0; i < n; i++) {\
        long long Z = x[i];\
        printf("%lld ", Z);\
    }\
    printf("\n");\
} while (0)

#define print_int_array_with_newlines(x, n) do {\
    for (int i = 0; i < n; i++) {\
        long long Z = x[i];\
        printf("%lld\n", Z);\
    }\
} while (0)

#define print_int(x) do {\
    long long Z = x;\
    printf("%lld\n", Z);\
} while (0)

void solve (long long N) {
    const int prime_sup = 1000000;
    bool prime[prime_sup];
    for (int i = 0; i < prime_sup; prime[i++] = true) {}
    prime[0] = prime[1] = false;

    { // エラトステネス
        int SUP = (int)sqrt(prime_sup);
        for (int i = 2; i < SUP + 10; i++) {
            for (int j = 2 * i; j < prime_sup; j += i) {
                prime[j] = false;
            }
        }
    }

    int cum_prime[prime_sup];

    {
        cum_prime[0] = 0;
        for (int i = 1; i < prime_sup; i++) {
            cum_prime[i] = cum_prime[i - 1];
            if (prime[i] == true) {
                cum_prime[i]++;
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < prime_sup; i++) {
        if (prime[i] == false) {
            continue;
        }
        if (1000 < i) {
            break;
        }
        for (int j = i + 1; j < prime_sup; j++) {
            if (prime[j] == false) {
                continue;
            }
            unsigned long long product = (long long)i * i * j * j;
            if (N < product) {
                break;
            } else {
                long long B = N / product;
                if (i < B) {
                    if (B < j) {
                        ans += cum_prime[B] - cum_prime[i];
                    } else {
                        ans += cum_prime[j - 1] - cum_prime[i];
                    }
                }
            }
        }
    }

    print_int(ans);
}

int main (void) {

    long long N = read_long_long();

    solve(N);

    return 0;
}

Submission Info

Judge Result