Submission #20537038

---

Source Code Expand

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {in_n: i64};
    let mut flag = [false; 100010];
    let mut count = 0;

    for i in 2..in_n {
        if i * i > in_n {
            break;
        } else if flag[i as usize] {
            continue;
        }

        flag[i as usize] = true;

        let mut v = i * i;

        while v <= in_n {
            count += 1;
            if v < flag.len() as i64 {
                flag[v as usize] = true;
            }

            v = v * i;
        }
    }

    println!("{}", in_n - count);
}

Submission Info

Judge Result