Editorial for Tìm số nguyên tố


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

var a,b,i,j,k:longint;
    d:array[1..200000] of boolean;

begin
     read(a,b);
     k:=trunc(sqrt(b));
     for i:=1 to k shr 1 do
         if not d[i shl 1+1] then
         begin
              j:=(i shl 1+1)*3;
              while j<=b do
              begin
                   d[j]:=true;
                   j:=j+(i shl 1+1) shl 1;
              end;
         end;
     d[1]:=true;
     for i:=a to b do
         if (i=2) or (odd(i) and not d[i]) then writeln(i);
end.

Code mẫu của happyboy99x

import java.util.Scanner;

public class Main {
    public static void main( String[] argv ) {
        boolean pr[] = new boolean[200005];
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt(), b = scan.nextInt();
        scan.close();
        for( int i = 2; i <= 200000; ++i ) pr[i] = true;
        for( int i = 2; i * i <= 200000; ++i ) {
            if ( !pr[i] ) continue;
            for( int j = i + i; j <= 200000; j += i ) pr[j] = false;
        }
        for( int i = a; i <= b; ++i )
            if (pr[i]) System.out.println(i);
    }
}

Code mẫu của ladpro98

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int a, b;
    cin>>a>>b;


    bool f[200005];
    for (int i = 2; i<=b; i++)
        f[i]=true;
    f[1]=false;

    int can = floor(sqrt(b));
    int i = 2;
    while (i<=can) {
          if (f[i]) 
          {
                  int j = i+i;
                  while (j<=b) 
                  {
                        f[j] = false;
                        j += i;
                  }
                  i++;
          }else
          {
               i++;               
          }

    }
    for(int i = a; i<=b; i++)
    if (f[i]) printf("%d\n", i);
    return 0;
}

Code mẫu của RR

a = raw_input().split()

L = int(a[0])
R = int(a[1])

sieve = [0] * (R + 11)
for i in range(2,500):
    if i == R:
        break;
    if sieve[i] == 0:
        j = i*i
        while j <= R:
            sieve[j] = 1
            j += i

sieve[0] = sieve[1] = 1

for i in range(L, R + 1):
    if sieve[i] == 0:
        print i

Code mẫu của hieult

#include<stdio.h>
#include<math.h>
main()
{ long n,m,t;
  scanf("%ld %ld",&m,&n);
  for(long j=m;j<=n;j++)
    {
    if(j==1)
      continue;
    t=0;
    for(long i=2;i<=sqrt(j);i++)
      {
      if(j%i==0)
        {
        t++;
        break;
        }
      }
    if(t==0)
    printf("%ld\n",j);
    }
}

Code mẫu của ll931110

Program PNUMBER;
        Const
                input  = '';
                output = '';
        Var
                a,b: longint;
                x: array[1..200000] of integer;

Procedure init;
          Var
                f: text;
          Begin
                Assign(f, input);
                        Reset(f);
                        Readln(f, a, b);
                Close(f);
                Fillchar(x, sizeof(x), 0);
                x[1]:= 1;
          End;

Procedure prime;
          Var
                f: text;
                i,k: longint;
          Begin
                For i:= 2 to trunc(sqrt(b)) do
                        If x[i] = 0 then
                                Begin
                                      k:= 2;
                                      While k * i <= b do
                                            Begin
                                                inc(x[k * i]);
                                                inc(k);
                                            End;
                                End;

                Assign(f, output);
                        Rewrite(f);
                        For i:= a to b do if x[i] = 0 then writeln(f, i);
                Close(f);
          End;

Begin
        init;
        prime;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   250000
long a,b,i;
bool prime[MAX+1];
void eratosthene(void)
{
     long i,j;
     prime[0]=true;
     prime[1]=true;
     for (i=2;i*i<=MAX;i=i+1)
         if (!prime[i])
            for (j=2*i;j<=MAX;j=j+i) prime[j]=true;
}
int main(void)
{
    eratosthene();
    scanf("%ld",&a);
    scanf("%ld",&b);
    for (i=a;i<=b;i=i+1)
        {
         if (!prime[i]) printf("%ld\n",i);
        }
}

Code mẫu của khuc_tuan

import psyco ; psyco.jit() 
from psyco.classes import *
def main():
    A,B=[int(x) for x in raw_input().split()]
    mark=[False for x in range(B+1)]
    for x in range(2,B+1):
        if not mark[x]:
            if x>=A: print x
            for y in range(x+x,B+1,x): mark[y]=True

psyco.bind(main)          # or method, class
newname = psyco.proxy(main)
newname()

Comments

Please read the guidelines before commenting.



  • 2
    ObitiDev  commented on June 27, 2022, 7:58 a.m.
    #include <bits/stdc++.h>
    
    #define FOR(i, l, r)    for(int i = l; i <= r; ++i)
    #define FOD(i, l, r)    for(int i = l; i >= r; --i)
    #define setp(x, y)      fixed << setprecision(x) << y;
    
    #define ll long long
    #define ug unsigned long long
    
    using namespace std;
        // Topic variable.
            int     a, b;
        // Auxiliary variable.
            bool    snt[200001];
        //___________________
    void sieve() {
        int e = sqrt(b);
        int i = 2;
        snt[1] = true;
        while (i <= e) {
            while (snt[i] == true) ++i;
            FOR(j, 2, b/i) snt[i*j] = true;
            ++i;
        }
    }
    int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL); cout.tie(NULL);
            cin >> a >> b;
            sieve();
            FOR(i, a, b) {
                if (!snt[i]) { cout << i << endl; }
            }
        return 0;
    }