Đếm số nguyên tố
Xem dạng PDFVới kiến thức đã học An biết rằng một số nguyên dương x là số nguyên tố khi x chỉ có 2 ước số dương là 1 và chính nó. An cũng biết rằng thuật toán tối ưu là tập hợp các bước giải một bài toán cụ thể sao cho sau khi áp dụng thuật toán đó ta thu được kết quả đúng và thoả mãn các ràng buộc về thời gian.
Trong giờ thực hành môn Tin học, giáo viên giao nhiệm vụ cho cả lớp lập trình giải quyết bài toán sau:
Cho hai số nguyên dương a,b (a≤b). Hãy đếm số lượng số nguyên tố thuộc đoạn a,b.
An đã hoàn chỉnh chương trình và đưa ra được kết quả trong giới hạn thời gian cho phép.
Em hãy lập trình bài toán để cùng đối chiếu với kết quả của bạn An nhé.
Yêu cầu:
Hãy đếm số lượng số nguyên tố thuộc đoạn [a,b] (a≤b).
Dữ liệu vào:
Từ tệp văn bản DEMNT.INP Gồm một dòng duy nhất chứa hai số nguyên dương a,b (a≤b≤10$^7$ ). Kết quả: Ghi ra tệp DEMNT. OUT gồm một dòng duy nhất là kết quả bài toán.
Ví dụ
| input | output |
|---|---|
| 1 5 | 3 |
Bình luận
include<bits/stdc++.h>
using namespace std;
define ll long long
ll a,b,i,dem; bool ngto(ll n) { ll i; if(n<2) return 0; for(i=2;i*i<=n;i++) if(n%i==0) return 0; return 1; } int main() { cin>>a>>b; dem=0; for(i=a;i<=b;i++) if(ngto(i)) dem++; cout<<dem; }
include<bits/stdc++.h>
using namespace std; #define ll long long ll n,s,i; bool ngto(ll 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 a, b; cin >> a; cin >> b;
}