Số nguyên tố cân bằng (HSG'21)
Xem PDF
Điểm:
300 (p)
Thời gian:
1.0s
Bộ nhớ:
640M
Input:
bàn phím
Output:
màn hình
Một số được gọi là số nguyên tố cân bằng nếu nó là số nguyên tố có \(2k + 1\) chữ số \((k \in \mathbb{N}^*)\), trong đó có \(2k\) chữ số giống nhau và có đúng \(1\) chữ số ở vị trí chính giữa (tức vị trí thứ \(k + 1\) từ trái sang phải) là khác với các chữ số còn lại.
Ví dụ: Số \(7778777\) là số cân bằng.
Yêu cầu:
Nhập từ bàn phím \(1\) số nguyên dương \(k\) \((k \le 7)\). Hãy tính và in ra màn hình số lượng các số nguyên tố cân bằng có \(2k + 1\) chữ số.
Example
Test 1
Input
3Output
7Note
Có \(7\) số nguyên dương có \(2 \times 3 + 1\) chữ số là số nguyên tố: \(1114111;1117111; 3331333; 3337333; 7772777; 7774777; 7778777\)
Bình luận
SPOILER ALERT
------------------------------
BRUTE FORCE (AC):
using namespace std;
bool snt(int n)
{
if (n < 2) return 0;
if (n < 4) return 1;
if (n % 2 == 0 || n % 3 == 0)
return 0;
for (int i = 5 ; i <= sqrt(n) ; i+=6)
if (n % i == 0 || n % (i+2) == 0) return 0;
return 1;
}
int a[10];
signed main()
{
int n; cin >> n;
for (int i = 1 ; i <= 9 ; i++) a[i] = i;
for (int i = 2 ; i <= n ; i++)
for (int j = 1 ; j <= 9 ; j++)
{
a[j] = a[j]10+j;
}
//test
int dem = 0;
for (int i = 0 ; i <= 9 ; i++)
for (int j = 1 ; j <= 9 ; j++)
{
long long ans = (a[j]10+i)*pow(10,n)+a[j];
if (snt(ans)) dem++;
}
cout << dem;
}
Dành cho những bạn nào bị bí ý tưởng có thể tham khảo. Mong mọi người đừng downvote!
12 bình luận nữa