Submission #67157335

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
import math
def solve():
    try:
        L, R = map(int, input().split())
    except (IOError, ValueError):
        return
    if L == R:
        print(1)
        return
    start = L + 1
    end = R
    found_prime_powers = set()
    limit = math.isqrt(end)
    primes_upto_limit = []
    sieve_primes = [True] * (limit + 1)
    if limit >= 0:
        sieve_primes[0] = False
    if limit >= 1:
        sieve_primes[1] = False
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

/*
import math

def solve():
    try:
        L, R = map(int, input().split())
    except (IOError, ValueError):
        return
    if L == R:
        print(1)
        return
    start = L + 1
    end = R
    found_prime_powers = set()
    limit = math.isqrt(end)
    primes_upto_limit = []
    sieve_primes = [True] * (limit + 1)
    if limit >= 0:
        sieve_primes[0] = False
    if limit >= 1:
        sieve_primes[1] = False
    for p in range(2, limit + 1):
        if sieve_primes[p]:
            primes_upto_limit.append(p)
            for i in range(p * p, limit + 1, p):
                sieve_primes[i] = False
    for p in primes_upto_limit:
        power = p * p
        while power <= end:
            if power >= start:
                found_prime_powers.add(power)
            if power > end // p:
                break
            power *= p
    is_prime_in_range = [True] * (end - start + 1)
    if start == 1 and len(is_prime_in_range) > 0:
        is_prime_in_range[0] = False
    for p in primes_upto_limit:
        start_val = max(p * p, (start + p - 1) // p * p)
        for j in range(start_val, end + 1, p):
            if j >= start:
                is_prime_in_range[j - start] = False
    for i, is_prime in enumerate(is_prime_in_range):
        if is_prime:
            found_prime_powers.add(start + i)
    print(1 + len(found_prime_powers))


if __name__ == "__main__":
    solve()
*/

#include <iostream>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

void solve() {
    long long L, R;
    if (!(cin >> L >> R)) {
        return;
    }

    if (L == R) {
        cout << 1 << endl;
        return;
    }

    long long start = L + 1;
    long long end = R;
    set<long long> found_prime_powers;

    long long limit = (long long)(sqrt(end));
    vector<long long> primes_upto_limit;
    vector<bool> sieve_primes(limit + 1, true);

    if (limit >= 0) sieve_primes[0] = false;
    if (limit >= 1) sieve_primes[1] = false;

    for (long long p = 2; p <= limit; ++p) {
        if (sieve_primes[p]) {
            primes_upto_limit.push_back(p);
            for (long long i = p * p; i <= limit; i += p) {
                sieve_primes[i] = false;
            }
        }
    }

    for (long long p : primes_upto_limit) {
        long long power = p * p;
        while (power <= end) {
            if (power >= start) {
                found_prime_powers.insert(power);
            }
            if (power > end / p) break;
            power *= p;
        }
    }

    vector<bool> is_prime_in_range(end - start + 1, true);
    if (start == 1 && is_prime_in_range.size() > 0) {
        is_prime_in_range[0] = false;
    }

    for (long long p : primes_upto_limit) {
        long long start_val = max(p * p, ((start + p - 1) / p) * p);
        for (long long j = start_val; j <= end; j += p) {
            if (j >= start) {
                is_prime_in_range[j - start] = false;
            }
        }
    }

    for (long long i = 0; i < is_prime_in_range.size(); ++i) {
        if (is_prime_in_range[i]) {
            found_prime_powers.insert(start + i);
        }
    }

    cout << 1 + found_prime_powers.size() << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:115:29: warning: comparison of integer expressions of different signedness: ‘long long int’ and ‘std::vector<bool>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  115 |     for (long long i = 0; i < is_prime_in_range.size(); ++i) {
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result