PTIT018A - ACM PTIT 2018 A - CẶP SỐ NGUYÊN TỐ ĐẶC BIỆT

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).

Input

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

Với mỗi test in ra số cặp nguyên tố tìm được trên một dòng

Example:

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++:

https://github.com/DuongLee98/SPOJ_PTIT/blob/main/PTIT018A.cpp

https://ideone.com/vsJJaR

#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:

...

PTIT017A - ACM PTIT 2017 A - ƯỚC SỐ NGUYÊN TỐ

Link Sub: http://www.spoj.com/PTIT/problems/PTIT017A/
Người Gửi: Sai

• Problem:

Cho các số nguyên A, B, K. Nhiệm vụ của bạn là hãy đếm xem trong đoạn [A, B] có bao nhiêu số có đúng K ước số nguyên tố.  
Ví dụ số 12 có 2 ước số nguyên tố (2 và 3), số 550 có 3 ước số nguyên tố (2, 5, và 11), trong khi số 17 chỉ có 1 ước số nguyên tố duy nhất là chính nó.
Input
Dòng đầu tiên là số lượng bộ test T (T ≤ 100).
Mỗi test gồm 3 số nguyên A, B, K (2 ≤ A, B ≤ 107, 1 ≤ K ≤ 109)

Output
Với mỗi test in ra chữ “Case” kèm theo số thứ tự bộ test và đáp án tìm được (theo mẫu như trong ví dụ).

Example:

Input

5
5 15 2
2 10 1
24 42 3
1000000 1000000 1
1000000 1000000 2

Output:

Case #1: 5
Case #2: 7
Case #3: 2
Case #4: 0
Case #5: 1

• Solution:

Chú Ý: Code dưới đây sub bằng C++6.3: time limit, C++4.3.2: 0.65s ??? Ý tưởng: - Sàng nguyên tố trong khoảng từ 1->10^7. (arr[]) - Mỗi nguyên tố xét duyệt các bội của nó. Bội của các số nguyên tố sẽ có ước là số nguyên tố đó -> dùng mảng đánh dấu (arr2[]) ghi nhận lại số ước số nguyên tố của số đó. VD: 1->5 -> (arr[1]=0, arr[2]=1, arr[3]=1, arr[4]=0, arr[5]=1); -> v[]={2, 3, 5} là các số nguyên tố. với v[0]=2 -> arr2[2]= 1, arr2[3]= 0, arr2[4]= 1, arr2[5]= 0; với v[1]=3 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 0; với v[3]=5 -> arr2[2]= 1, arr2[3]= 1, arr2[4]= 1, arr2[5]= 1; -> Vậy arr2[i] tương đương với số ước nguyên tố của i;

• Code:

C++:

https://ideone.com/HyEtOE

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <vector>
#define MAX 10000000
using namespace std;


long arr[10000007];
long arr2[10000007];
void init ()
{
    for (long i=1; i<=MAX; i++)
    {
        arr[i]=1;
        arr2[i]=0;
    }
    arr[1]=0;
}

void sangNT ()
{
    for (long i=2; i<=sqrt(MAX); i++)
    {
        if (arr[i]==1)
        {
            for (long j=2; j<=MAX/i; j++)
            { 
                arr[j*i]=0;
            }
        }
    }
}

int main ()
{
    init ();
    sangNT ();
    vector <long> v;
    for (long i=1; i<=MAX; i++)
    {
        if (arr[i]==1) v.push_back(i);
    }
    for (long i=0; i<v.size(); i++)
    {
        for (long j=1; j<=MAX/v[i]; j++)
        {
            arr2[v[i]*j]++;
        }
    }
    int t;
    cin>>t;
    for (int k=1; k<=t; k++)
    {
        long A, B, K, count=0;
        cin>>A>>B>>K;
        for (long i=A; i<=B; i++)
        {
            if (arr2[i]==K) count++;
        }
        printf ("Case #%d: %ld\n", k, count);
    }
    
    return 0;
}

JAVA:

P134SUMF - SUM4 F - Sàng nguyên tố

Link Sub: http://www.spoj.com/PTIT/problems/P134SUMF/
Người Gửi: Sai

• Problem:

Tí và Tèo đang cùng nhau học về sàng nguyên tố Eratosthenes.

Thuật toán sàng nguyên tố để tìm các số nguyên tố từ 2 tới N như sau:

1. Viết tất cả các số nguyên từ 2 tới N theo đúng thứ tự.

2. Tìm số nguyên nhỏ nhất chưa bị gạch. Gọi số đó là P. P sẽ là số nguyên tố.

3. Gạch bỏ P và tất cả các bội của nó.

4. Nếu tất cả các số chưa bị gạch bỏ, quay lại bước 2.

Tí đố Tèo rằng, cho trước N và K, hãy tìm số thứ K sẽ bị gạch bỏ.

Input
Chứa 2 số nguyên N và K (2 ≤ K < N ≤ 1000).

Output
Hãy in ra số thứ K sẽ bị gạch bỏ.

Example:

Input

7 3

Output:

6

Input

15 12

Output:

7

Input

10 7

Output:

7

9

• Solution:

Giải thích test 3: Các số lần lượt bị gạch bỏ sẽ là 2, 4, 6, 8, 10, 3, 9, 5, 7.  
Do đó số thứ 7 sẽ là 9.
Theo quy tắc mà làm thôi :v

• Code:

C++:

JAVA: