SkullBox Forum  |  Development  |  Concursuri de programare  |  Topic: [Incepatori][Concurs Nr. 26]Numere prime

1 5000000

#include <fstream.h>
#include <math.h>
int prim(long x)
{
int g=1;
for(int i=2;i<=sqrt(x);i++)
if(x%i==0) g=0;
return g;
}

int main()
{
int a,c=0;
long b;

ifstream f("prime.in");
ofstream g("prime.out");

f>>a; f>>b;
if(a==1) c=-1;

for(long i=a;i<=b;i++)
if(prim(i)) c++;

g<<c<<" numere prime in intervalul ["<<a<<","<<b<<"]."<<endl;

f.close();
g.close();
return 0;

}

program Concurs26;

const p16:array[0..15] of word = (2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53);
var   a,b,x,suma:longint;
      k:word;
      p333:array[0..332] of word;

procedure NextPrime;assembler;
asm
  mov bx,k
  cld
@Start:
  mov si,offset p16
@TryNext:
  lodsw
  mov di,ax
  xor dx,dx
  mov ax,bx
  div di
  or  dx,dx
  jz @FactorFound
  cmp ax,di
  ja @TryNext
  jmp @Stop
@FactorFound:
  add bx,2
  jmp @Start
@Stop:
  mov word ptr k,bx
end;

procedure NextPrime32;assembler;
asm
  db $66; mov bx,word ptr x
  cld
@Start:
  mov si,offset p333
@TryNext:
  db $66; xor ax,ax
  lodsw
  db $66; mov di,ax
  db $66; xor dx,dx
  db $66; mov ax,bx
  db $66; div di
  db $66; or  dx,dx
  jz @FactorFound
  db $66; cmp ax,di
  ja @TryNext
  jmp @Stop
@FactorFound:
  db $66; db $83; db $c3; db $02;
  jmp @Start
@Stop:
  db $66; mov word ptr x,bx
end;

procedure init;
var f:text;
    i:word;
begin
  assign(f,'prime.in');
  {$i-}
  reset(f);
  {$i+}
  if ioresult<>0 then begin
    writeln('Lipseste fisierul prime.in');
    halt;
  end;
  read(f,a);
  read(f,b);
  close(f);
  if ( (b>5000000) or (a<1) ) then begin
    writeln('Fisierul prime.in trebuie sa contina 2 numere in intervalul 1..5000000');
    halt;
  end;
  { construim un sir de 333 de numere prime necesare pentru a factoriza
    un numar de pina in 5000000
  }
  for i:=0 to 15 do p333[i]:=p16[i];
  k:=p333[i];
  repeat
    k:=k+2;
    NextPrime;
    inc(i);
    p333[i]:=k;
  until k>2237;   { 2237*2237 = 5004169 > b }
  {write('i=',i); { i=332; intre 0 si 332 sunt 333 de numere }
end;

procedure run;
begin
  suma:=0;
  if b<a then exit;

  x:=a;
  if (x mod 2) =0 then inc(x);
  if a=b then begin
    if a=1 then exit;
    if a=2 then begin suma:=1; exit; end;
    NextPrime32;
    if x>b then exit;
  end;
  if a<3 then inc(suma);
  if a=1 then x:=3;
  { ^ cam aiurea dar necesar pentru cazurile particulare }

  repeat
    NextPrime32;
    if(x<=b) then inc(suma);
    x:=x+2;
  until x>b;
 
  { puteam sa memorez numerele prime pina in 5.000.000 intr-un fisier
    pentru ca la urmatoarea executie sa mearga si mai repede
    dar e suficient de rapid (mai putin de 10 secunde).
  }
end;

procedure done;
var f:text;
begin
  assign(f,'prime.out');
  rewrite(f);
  write(f,suma);
  close(f);
end;

begin
  init;
  run;
  done;
end.

program Project1;

{$APPTYPE CONSOLE}

uses Windows, SysUtils;

const LookupPrime : array [1..332] of word =
      (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
       97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191,
       193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
       307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
       421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
       547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
       659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787,
       797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
       929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
       1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129,
       1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249,
       1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367,
       1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481,
       1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579,
       1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
       1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801,
       1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931,
       1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039,
       2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143,
       2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237);

var nStart, nFinish, prCounter, tStart, prim : Longint;

procedure ReadFile;
var fPrime: TextFile;
    fName: String;
begin
  fName := ExtractFilePath(ParamStr(0)) + 'prime.in';
  if FileExists(fName) then
    begin
      try
        AssignFile(fPrime, fName);
        try
          ReSet(fPrime);
          Read(fPrime, nStart, nFinish);
          if (nStart < 1) or (nStart > 5000000) or
             (nFinish < 1) or (nFinish > 5000000) then
            begin
              Write('Oopsie daisy ... allowed numbers are between 1 and 5 millions.');
              Sleep(2500);
              halt(0);
            end;

          if nStart > nFinish then
            begin
              nStart := nStart + nFinish;
              nFinish := nStart - nFinish;
              nStart := nStart - nFinish;
            end;
        finally
          CloseFile(fPrime);
        end;
      except
        Write('Weird error found : finders keepers !');
      end;
    end
    else
      begin
        Write('Fisierul "prime.in" lipseste !');
        Sleep(2500);
        Halt(0);
      end;
end;

procedure ComputePrimeNumbers;
var iCounter, cnt, radNr: Longint;
    ePrim, impar: Boolean;
begin
  prCounter := 0;
 
  prim := 0;
  impar := False;

  iCounter := nStart;
  while iCounter <= nFinish do
    begin
      radNr := Round(Sqrt(iCounter));

      ePrim := True;
      cnt := 1;

      while cnt <= 332 do
        begin
          if LookupPrime[cnt] > radNr
            then Break;

          if (iCounter mod LookupPrime[cnt] = 0) then
            begin
              ePrim := False;
              Break;
            end;
          Inc(cnt); 
        end;

      if ePrim
        then inc(prCounter);

      if (not Impar) then
        if Odd(iCounter)
          then Impar := True;

      if Impar
        then Inc(iCounter, 2)
        else Inc(iCounter);
    end;
end;

procedure WriteFile;
var fPrime: TextFile;
    fName: String;
begin
  fName := ExtractFilePath(ParamStr(0)) + 'prime.out';
  try
    AssignFile(fPrime, fName);
    try
      ReWrite(fPrime);
      Writeln(fPrime, prCounter);
    finally
      CloseFile(fPrime);
    end;
  except
    Write('Weird error found : finders keepers !');
  end;
end;

begin
  ReadFile;

  ComputePrimeNumbers;

  WriteFile;
end.

#include<iostream>
#include<bitset>
#include<algorithm>
#define DIM 2500001
using namespace std;
bitset <DIM> prime;
int main()
{
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
prime.set();
long a, b, n=0, i, di, j, aux;
cin>>a>>b;
for(i=3;i<=b;i+=2)
         if(prime[(i-3)>>1])for(di=i+i,j=i+di;j<=b;j+=di)prime[(j-3)>>1]=0;
for(aux=max(a,(long)3),i=aux+!(aux%2);i<=b;i+=2){n+=prime[(i-3)>>1];}
cout<<n+(a<=2&&b>1);
}