Concursul s-a incheiat. Sursele:
nichietheone:#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.
AdyX:
Nu a trimis sursa.
1. nichietheone - programul este corect dar foarte incet din cauza metodei prin care verifica daca un numar este sau nu prim.
2. emi - program corect, destul de rapid.
3. DarkByte - program corect, mai rapid decat al lui emi.
4. AdyX - program gresit.
O varianta foarte rapida, fara a folosii preprocesare, folosind Ciurul lui Erathostene:
#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);
}
Castigator: DarkByte. Dintre toate programele, al lui este de departe cel mai rapid
.
Bafta tuturor la noul concurs
.
L.E.: Merci de atentionare, am modificat
.
