1423K - Lonely Numbers - CodeForces Solution

binary search math number theory two pointers *1600

Please click on ads to support us..

Python Code: 

import os,io
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
p=[0]*1000002
s=p[:]
s[1]=1
for j in range(2,1000001):
    if p[j]==0:
        for k in range(j+j,1000001,j):
            p[k]=1
    s[j]=s[j-1]+1-p[j]
n=int(input())
a=list(map(int,input().split()))
for v in a:
    q=int(v**(0.5))
    print(s[v]-s[q]+1)

C++ Code: 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long long int lli;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<ll> vl;
typedef vector<lli> vli;
typedef vector<double> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define res resize
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
#define lsb(x) x&(-x)

const ll MOD = 1e9 + 7;
const char nl = '\n';
const int MAX = 3e5 + 5;
const double eps = 1e-18;

void solve() {
    int tt;
    cin >> tt;

    int n = 1e6;
    vi is(n, 1);
    is[0] = is[1] = 0;
    for(int i=4; i<=n; i += 2) is[i] = 0;
    for(int i=3; i*i<=n; i+=2) {
        if(is[i]) {
            for(int j=i*i; j<=n; j+=2*i) is[j] = 0;
        }
    }

    for(int i=0; i<=n; i++) {
        is[i] += is[i-1];
    }

    while(tt--) {
        int nn;
        cin >> nn;

        int l = sqrt(nn);
        cout << is[nn] - is[l] + 1 << nl;
        
    }
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    solve();
    return 0;
}


Comments

Submit
0 Comments
More Questions

1217. Minimum Cost to Move Chips to The Same Position
347. Top K Frequent Elements
1503. Last Moment Before All Ants Fall Out of a Plank
430. Flatten a Multilevel Doubly Linked List
1290. Convert Binary Number in a Linked List to Integer
1525. Number of Good Ways to Split a String
72. Edit Distance
563. Binary Tree Tilt
1306. Jump Game III
236. Lowest Common Ancestor of a Binary Tree
790. Domino and Tromino Tiling
878. Nth Magical Number
2099. Find Subsequence of Length K With the Largest Sum
1608A - Find Array
416. Partition Equal Subset Sum
1446. Consecutive Characters
1618A - Polycarp and Sums of Subsequences
1618B - Missing Bigram
938. Range Sum of BST
147. Insertion Sort List
310. Minimum Height Trees
2110. Number of Smooth Descent Periods of a Stock
2109. Adding Spaces to a String
2108. Find First Palindromic String in the Array
394. Decode String
902. Numbers At Most N Given Digit Set
221. Maximal Square
1200. Minimum Absolute Difference
1619B - Squares and Cubes
1619A - Square String