MK119SNT - Đếm số nguyên tố
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho hai số nguyên dương ~L ≤ R~. Hãy đếm xem trong đoạn ~[L, R]~ có bao nhiêu số nguyên tố.
Input
- Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
- ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L ≤ R~ cách nhau bởi một dấu cách.
Giới hạn:
- ~1 ≤ T ≤ 10^2, 1 ≤ L ≤ R ≤ 10^6~.
Output
- Với mỗi cặp số ~L~ và ~R~, ghi ra trên một dòng số số nguyên tố trong đoạn ~[L, R]~.
Sample
Input #1
2
2 3
10 15
Output #1
2
2
Problem source: Chuyên Sơn La Online Judge
Bình luận
include <stdio.h>
int main() { // Sang nguyen to long A[1000001]; for (long i = 2; i <= 1000000; i++) { A[i] = 1; } for (long i = 2; i <= 1000000; i++) { if (A[i] == 0) continue; long long j = 2 * i; while (j <= 1000000) { A[j] = 0; j += i; } } // Dem so nguyen to int Count[1000001]; Count[2] = 1; for (long i = 3; i <= 1000000; i++) { Count[i] = Count[i - 1] + A[i]; } // Test int T; scanf("%d", &T); while (T--) { long n, k; scanf("%ld %ld", &n, &k); if (A[n] == 0 && A[k] == 0) printf("%d\n", Count[k] - Count[n]); else printf("%d\n", Count[k] - Count[n] + 1); } return 0; }
mn xem code giúp em có sai ở đâu không mà bị sai case 5 7 8 9 10 với ạ.
include<iostream>
include<cmath>
using namespace std;
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; }
int main() { int t; cin >> t; while (t--) { int a, b; cin >> a >> b; int count = 0; for (int i = a; i <= b; i++) { if (is_prime(i)) count++; } cout << count << endl; } return 0; } co cach nao de sua loi tle khong a?
Bạn sử dụng sàng số nguyên tố nhé
https://www.ideone.com/zrSgeX
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
sàng+prefix sum
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.