Link Sub: https://www.spoj.com/PTIT/problems/PTIT018A/
Người Gửi: Dương Lee
- Problem:
Cặp số nguyên tố P, Q được gọi là cặp nguyên tố đặc biệt nếu P và Q là nguyên tố và hơn kém nhau 6 đơn vị. Ví dụ các cặp nguyên tố (11, 17), (13, 19) được gọi là cặp nguyên tố đặc biệt. Hãy đếm tất cả các cặp nguyên tố đặc biệt trong khoảng [L, R].
Ví dụ L=6, R=59 ta có 10 cặp nguyên tố đặc biệt là (7, 13), (11, 17), (13,19), (17, 23), (23, 29), (31, 37), (37, 43), (41, 47), (47, 53), (53, 59).
Dòng đầu tiên là số lượng bộ test T (T≤100).
Mỗi bộ test gồm 2 số nguyên L, R (2≤L, R≤10^6).
Output
Example:
Với mỗi test in ra số cặp nguyên tố tìm được trên một dòng
Input
3
11 19
6 59
2 1000000
Output:
2
10
16386
- Solution:
- Sử dụng sàng nguyên tố: Khởi tạo được một mảng đánh dấu các số là số nguyên tố (snt[], trong đó nếu snt[i]=1 thì i là số nguyên tố)
- Trong một khoảng L, R: (i:=L->R) ta có một cặp nếu số thứ i và số thứ i+6 là cùng là số nguyên tố (snt[i]=1 && snt[i+1]=1)
- Code:
C++:
#include <iostream>
#include <math.h>
using namespace std;
#define MAX 1000000
int snt[MAX+10];
int mcd[MAX+10];
int sont(int n)
{
if (n<2)
return 0;
for (int i=2; i<=sqrt(n); i++)
{
if (n%i==0)
{
return 0;
}
}
return 1;
}
void init()
{
for (int i=1; i<=MAX; i++)
{
snt[i] = 1;
mcd[i] = 0;
}
}
void sangnt()
{
snt[0] = 0;
snt[1] = 0;
for (int i=2; i<=sqrt(MAX); i++)
{
if (snt[i] == 1)
{
for (int j=2; j<=MAX/i; j++)
{
snt[i*j] = 0;
}
}
}
}
int main()
{
init();
sangnt();
int t;
cin>>t;
while(t--)
{
int a, b;
cin>>a>>b;
int ts = 0;
for (int i=a; i<=b; i++)
{
if (snt[i]==1 && snt[i+6]==1 && i+6<=b)
{
ts++;
}
}
cout<<ts<<endl;
}
return 0;
}JAVA:
...Python:
...