Tìm số nguyên tố

View as PDF

Submit solution

All submissions

Read editorial

Points: 0.01 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem source:

Dân gian

Problem type

Allowed languages

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy tìm tất cả các số nguyên tố trong đoạn ~[A~, ~B]~.

Input

Gồm ~2~ số nguyên ~A~ và ~B~ cách nhau bởi ~1~ dấu cách ~(1 \leq A \leq B \leq 200000)~.

Output

Ghi ra tất cả các số nguyên tố trong đoạn ~[A~, ~B]~ theo thứ tự tăng dần. Mỗi số trên ~1~ dòng.

Sample Input

1 10

Sample Output

Comments

Comments

Please read the guidelines before commenting.

0

ToniKroos commented on May 7, 2026, 2:36 a.m. ← edit 3 →

Dùng sàng số nguyên tố ý, bị mỗi cái a,b<=200000 nên có k/n TLE

def returnenallesprime(x): primes=[] arch=[1](x+1) for i in range(2,x+1): if arch[i]: primes.append(i) for i in range(ii,x+1,i): arch[i]=0 return primes a,b=map(int,input().split()) v=returnenallesprime(b) for i in v: if i>=a: print(i)

0

ToniKroos commented on May 7, 2026, 2:36 a.m.

à sorry, thiếu mấy cái input với nhầm 200000 thành 1e6 nhed, sorry mn

0

nguyentanlocefootball commented on Dec. 25, 2025, 12:31 p.m.

include <bits/stdc++.h>

using namespace std; bool isPrime(int n){ if (n<2) return false; else{ for (int i=2;i*i<=n;i++){ if (n%i==0) return false; } return true; } } int main(){ iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); int a,b; cin>>a>>b; for (int i=a;i<=b;i++){ if (isPrime(i)) cout<<i<<endl; } }

vominhmanh10 commented on Oct. 31, 2025, 10:08 a.m. ← edited →

đang luyện code miller-rabin

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
def prime(n):
    for p in primes:
        if n % p == 0: return n == p
    if n < 41: return False
    k, m = 0, n - 1
    while (m & 1) == 0:
        k += 1
        m >>= 1
    for p in primes:
        mod = pow(p, n - 1, n)
        if mod == n - 1 or mod == 1: continue
        for i in range(1, k):
            mod = mod ** 2 % n
            if mod == n - 1: break
        else: return False
    return True
l, r = map(int, input().split())
for x in range(l, r + 1):
    if prime(x):
        print(x)

-5

hongthuy_tranchung commented on March 7, 2025, 11:11 a.m.

include<bits/stdc++.h>

using namespace std; bool snt(long long n){ if(n==2||n==3) return true; if(n<2||n%2==0||n%3==0) return false ; long long k=-1,cbh=trunc(sqrt(n)); while(k<=cbh){ k+=6; if(n%k==0||n%(k+2)==0) break; } return (k>cbh); } int n; int main() { long long A,B; cin>>A>>B; for(int i=A;i<=B;i++) if(snt(i)) cout<<i<<endl; return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

-6

pthtuong29 commented on Jan. 8, 2025, 8:08 a.m.

include<iostream>

include<vector>

using namespace std; typedef long long ll; ll l,k; void sang(ll l,ll k){ vector<bool> A(k+1,true); A[0]=A[1]=false; for(ll i=2;ii<=k;i++){ if(A[i]) { for(ll j=ii;j<=k;j+=i) A[j]=false; } } for(ll i=l;i<=k;i++) { if(A[i]) cout<<i<<"\n"; } } int main(){ cin>>l>>k; sang(l,k); }

This comment is hidden due to too much negative feedback. Show it anyway.

2

ducquoc commented on Dec. 30, 2024, 3:47 a.m. ← edited →

Java template (Delegate Quick Scanner) for faster IO (e.g. constraint 0.3s instead of 1s)

https://oj.vnoi.info/src/8029681

(the template is re-usable for other problems)

-5

quygiaminh123 commented on Dec. 29, 2024, 12:08 p.m.

include<bits/stdc++.h>

using namespace std; bool kt(long long b) { if(b<2) return false; for (int i=2;i<=sqrt(b);i++) { if(b%i==0) { return false; } } return true; } int main() { long long a,b; cin>>a>>b; for(int i=a;i<=b;i++) { if(kt(i)) { cout<<i<<endl; } } return 0; }

This comment is hidden due to too much negative feedback. Show it anyway.

-12

kietjumper commented on Aug. 25, 2024, 5:00 p.m. ← edit 3 →

https://codebeautify.org/cpp-formatter-beautifier/y2424595e

This comment is hidden due to too much negative feedback. Show it anyway.

-9

kietjumper commented on Aug. 25, 2024, 5:03 p.m.

Tham Khao Nhe. Dung thi cho 1 upvote nhe <3

This comment is hidden due to too much negative feedback. Show it anyway.

-9
Trau_4 commented on July 26, 2024, 8:49 a.m.
include <bits/stdc++.h>

using namespace std;

define ll long long

define eb emplace_back

const ll mod=1000000007; const ll rx[]={1, 0, -1, 0}; const ll ry[]={0, -1, 0, 1}; int arr[200005]; void sang() { for(int i=2;i<200005;i++) { arr[i]=1; } for(int i=2;i<200005;i++) { if(arr[i]==1) { for(int j=i*2;j<200005;j=j+i) { arr[j]=0; } }

}

} ll m, n; int main() { ll a, b, c; iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); //freopen("LAMP.inp", "r", stdin); freopen("LAMP.out", "w", stdout); //freopen("E:/a1.txt", "r", stdin), freopen("E:/a2.txt", "w", stdout); sang(); cin>>a>>b; for(c=a;c<=b;c++) { if(arr[c]==1) { cout<<c<<"\n"; }

}

}
This comment is hidden due to too much negative feedback. Show it anyway.

-6

hohoanghai5042011 commented on July 12, 2024, 2:11 p.m.

This comment is hidden due to too much negative feedback. Show it anyway.

-2

kietjumper commented on Aug. 25, 2024, 5:15 p.m.

Lan sau Spoil nhe!

-7

zatarainbow commented on July 7, 2024, 6:53 a.m.

include <bits/stdc++.h>

long long a,b; long long kt(long long a) { long long i=2; for(i;i*i<=a;i++) if(a%i==0) return false; return true; } using namespace std; int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);cout.tie(NULL); cin>>a>>b; if(a<=2) a=2; for(a;a<=b;a++) { if(kt(a)==true) cout<<a<<'\n'; } }

max ping by top1zata.blogspot.comcom

This comment is hidden due to too much negative feedback. Show it anyway.

0

ChiPhatNguyen commented on June 23, 2024, 4:08 a.m.

Links https://youtu.be/U8eNPUUpN6A?si=V6Fg7O1nDCVdU1de* video về sàng cho ae nào chưa bt*

-2

ChiPhatNguyen commented on June 23, 2024, 4:04 a.m. ← edit 7 →

include <bits/stdc++.h>

using namespace std;

bool snt(int n){

if(n < 2) return false;

for(int i = 2;i<=sqrt(n);i++){

    if(n%i==0) return false;

}

return true;

} int prime[100000];

void sang(){

for(int i = 1;i<=1000000;i++){

    prime[i] = 1;

}

prime[0] = prime[1] = 0;

for(int i = 2;i<=sqrt(10000000);i++){

    if(prime[i]==1){

        for(int j = i*i;j<=1000000;j+=i)

        prime[j] = 0;

    }

}

} int main(){

int a,b;

cin>>a>>b;

sang();

for(int i = a;i<=b;i++){

    if (prime[i]==1)

    cout << i << " " << endl; /// sai = + 1 loli

}

return 0;

}

https://youtu.be/U8eNPUUpN6A?si=V6Fg7O1nDCVdU1de

sao lại ko AC full v nhnhỉ

-1

winky commented on April 27, 2024, 7:11 p.m.

bài này dùng miller rabin nha

2

lemonpro134 commented on May 3, 2024, 1:03 p.m.

dùng sàng thôi cx đủ rồi

-17

ElmiraAthena commented on Feb. 1, 2024, 1:14 a.m.

Cristiano Ronaldo! Ronaldo! Ronaldo! Goal!!! Siuuuuuuuuuuuuuu

This comment is hidden due to too much negative feedback. Show it anyway.

-1

kietjumper commented on Aug. 25, 2024, 5:15 p.m.

Cai Gi Vay Ban???

7

thanhhoang commented on Jan. 23, 2024, 6:50 p.m.

Dùng sàng nguyên tố.

0

khoitran commented on Jan. 13, 2024, 8:39 a.m.

Bài này cứ dùng sàng là ok

-95

nthquan_1505 commented on March 30, 2023, 4:22 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.

-90

nthquan_1505 commented on March 30, 2023, 4:22 a.m.

xin downvote

This comment is hidden due to too much negative feedback. Show it anyway.