[CSP - TS10 - 2025] Bài 1: Ước nguyên tố

Điểm: 10,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

Với một số nguyên dương ~x \ge 2~, gọi ~f(x)~ là ước số nguyên tố lớn nhất của ~x~.

Yêu cầu: Cho số ~n~ và ~q~ câu hỏi, mỗi câu hỏi cho bởi số nguyên dương ~k~. Bạn hãy cho biết trong phạm vi từ 2 tới ~n~ có bao nhiêu giá trị ~x~ mà ~f(x) \le k~.

Input

Dòng 1 chứa hai số nguyên dương ~n, q~ cách nhau bởi dấu cách (~2 \le n \le 10^6; q \le 10^6~).
~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~ ứng với một câu hỏi (~2 \le k \le n~).

Output

Ghi ra ~q~ dòng, ứng với mỗi câu hỏi, ghi ra một số nguyên trên một dòng là đáp số của câu hỏi tương ứng.

Sample Input 1

Sample Output 1

Từ 2 tới 10 có:

3 số ~x~ có ~f(x) \le 2~: 2, 4, 8
8 số ~x~ có ~f(x) \le 5~: 2, 3, 4, 5, 6, 8, 9, 10
6 số ~x~ có ~f(x) \le 3~: 2, 3, 4, 6, 8, 9
9 số ~x~ có ~f(x) \le 8~: 2, 3, 4, 5, 6, 7, 8, 9, 10

Subtasks

60% số điểm ứng với các test có ~n \le 10^4; q \le 10~.
40% số điểm ứng với test không có ràng buộc bổ sung.

Bình luận

Hãy đọc nội quy trước khi bình luận.

tikl20tok đã bình luận lúc 4, Tháng 3, 2026, 10:54

code day nha mn

include<bits/stdc++.h>

using namespace std; bool a[(long long)1e6+10];

int main() {

ios::sync_with_stdio(false);
cin.tie(NULL);

long long n,q;
cin>>n>>q;
long long i,j;
memset(a,true,sizeof(a));
//sang era
a[0]=false;
a[1]=false;
for (j=4;j<=(long long)1e6+5;j+=2)//xu li rieng so 2
{
    a[j]=false;
}
for (i=3;i*i<=(long long)1e6+5;i+=2)
{
    if (a[i]==true)
    {
        for (j=i*i;j<=(long long)1e6+5;j+=i)
        {
            a[j]=false;
        }
    }
}
//end
//khoi tao vector so nguyen to
vector&lt;long long> snt;
snt.reserve(10000);
snt.push_back(0);//de sau do bat dau tu index 1
long long demsnt=0;
for (i=1;i<=(long long)1e6+5;i++)//hoan thanh viec tach cach so nguyen to
{
    if (a[i]==true)
    {
        demsnt+=1;
        snt.push_back(i);
    }
}
//end

//lay uoc so nguyen to lon nhat cua moi so
vector&lt;long long> truyvan((long long)1e6+10,0);

//bat dau viec ghi de
for (i=1;i<=demsnt;i++)
{
    for (j=snt[i];j<=n;j+=snt[i])
    {
        truyvan[j]=snt[i];
    }
}
//end

vector&lt;long long> truyq((long long)1e6+10,0);
//hoan tat viec lay so cac so co uoc snt lon nhat
for (i=2;i<=n;i++)
{
    truyq[truyvan[i]]+=1;//snt lon nhat, so luong
}
//hoan thanh mang truy van q
for (i=3;i<=n;i++)
{
    truyq[i]+=truyq[i-1];
}
//end

//bat dau truy van
for (i=1;i<=q;i++)
{
    cin>>j;
    cout<&lt;truyq[j]<<"\n";
}



return 0;

}