SANGNT - Thuật toán Sàng 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:
0.1s
C#
0.3s
Java
0.3s
Python 3
0.5s
Giới hạn bộ nhớ:
256M
C#
250M
Java
250M
Python 3
250M
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
Một số nguyên dương ~n > 1~ được gọi là số nguyên tố nếu nó không có ước nguyên dương ngoài ~1~ và chính nó (hay không có ước nguyên dương thực sự khác ~1~).
Yêu cầu:
Cho số nguyên dương ~n~, hãy liệt kê tất cả các số nguyên tố nhỏ hơn hoặc bằng ~n~.
Input
- Gồm một số nguyên dương ~n~.
Giới hạn:
- ~1 ≤ n ≤ 10^6~.
Output
- Ghi ra trên một dòng các số nguyên tố nhỏ hơn hoặc bằng ~n~, các số được ghi ra theo thứ tự tăng dần, hai số liên tiếp cách nhau một dấu cách.
Sample
Input #1
3
Output #1
2 3
Input #2
10
Output #2
2 3 5 7
Problem source: Chuyên Sơn La Online Judge
Bình luận
#include <bits/stdc++.h>
using namespace std; long long f[1000001],i=0,j=0,n; int main() { cin>>n; f[1]=1; for(i=2;i<=1000;i++) if(f[i]==0) for (j=i*i;j<=1e6;j+=i) f[j]=1; for (i=1;i<=n;i++) if (f[i]==0) cout<<i<<" "; }
include<bits/stdc++.h>
using namespace std; int a[10000001]; void sang(){ for(int i=0;i<=10000001;i++){ a[i]=1; } a[0]=a[1]=0; for(int i=2;i<=sqrt(10000001);i++){ if(a[i]==1) { for(int j=i*i;j<=10000001;j+=i){ a[j]=0; } } } } int main(){ iosbase::syncwith_stdio(false); cin.tie(0);cout.tie(0); sang(); int n; cin>>n; for(int i=1;i<=n;i++){ if(a[i]==1) cout<<i<<" "; } return 0; }
Sang nguyen to
import math
def isPrime(x):
""" def sangNT(x):
n = int(input()) print(sangNT(n)) """ def sannNT(x): A = [True for i in range(x+1)] A[0] = A[1] = False for i in range(2,x+1): if(A[i]==True): for j in range(i*i,x+1,i): A[j] = False return [i for i in range(x+1) if(A[i]==True)] n = int(input()) SNT = sannNT(n) for i in range(len(SNT)): print(SNT[i],end = " ")
include <bits/stdc++.h>
using namespace std; bool a[1000006]; int main() { int i,j,n; cin>>n; for(i=2;i<=n;i++)a[i]=1; for(i=2;i<=n;i++)if(a[i]) for (j=2*i;j<=n;j+=i)a[j]=0; for(i=2;i<=n;i++)if(a[i])cout<<i<<" "; }
ai có code python cho mình tham khảo với ạ
Anh ơi bên C++ có 0.1s giới hạn thôi hả anh. Anh có thể tăng lên không ạ
Bạn dùng sàng số nguyên tố nhé
Code C++ cho ai chưa AC nè nếu thấy hay up vote cho mik nha
include<bits/stdc++.h>
using namespace std;
define int long long
int n; int a[1000001]; void solve() {
} main() {
}
bạn nào AC python cho mình tham khảo với
def snt(n):
n = int(input()) primes = snt(n) print(' '.join(primes),end='')
n = int(input()) def sangnt(n): f = [False,True]*((n+1)//2)+[False] f[1],f[2] = False,True for i in range(3,int(n**0.5)+1,2): if f[i]: for p in range(i*i,n+1,i):f[p] = False return [x for x in range(2,n+1) if f[x]] res = sangnt(n) print(' '.join(map(str,res))) 0,2s bạn nhé
bài này lên tăng thời gian cho Java anh ạ
Anh để 0.3s cho Java rồi, em thử lại nhé b21dccn441