Numere prime

Rezolvarea problemelor de matematica prin realizarea unor programe.
noobakaflo
utilizator
utilizator
Mesaje: 34
Membru din: 03 Noi 2010, 21:35

Numere prime

Mesaj de noobakaflo » 06 Dec 2010, 21:03

Salut din nou.
O problema de 'incepator' dupa infoarena..

Suna cam asa:

Gheorghe a invatat la scoala despre numere prime. A invatat ca un numar este prim, daca se divide doar cu 1 si cu el insusi(1 nu este considerat numar prim). A aflat ca exista algoritimi foarte eficienti care pot determina daca un numar este prim sau nu, in timp chiar sub polinomial. Din pacate acesti algoritmi sunt foarte complicati, si Gheorghe s-a gandit la o aproximare. Idea lui este sa consideri un numar prim daca nu se divide la primele K numere prime.

Cerinta
Demonstreaza ca ideea lui Gheorghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N care nu este divizibil cu primele K numere prime, dar nu este prim.
Date de intrare
Pe prima linie din fisierul prim.in se va afla numarul K.
Date de iesire
Pe prima linie a fisierului prim.out se va gasi numarul N cautat.

Restrictii
1 ≤ K ≤ 100.000


Exemplu: prim.in 1 prim.out 9

Explicatii
9 nu este divizibil cu 2 si nu este nici prim.prim.in

Exemplu: prim.in 3 prim.out 49
Explicatii
Primele 3 numere prime sunt 2, 3, 5. Numerele care nu sunt divizibile cu 2, 3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49, .. 49 este cel mai mic numar care nu este prim.

Cum am gandit eu rezolvarea ?

Pai trebuie sa afisezi patratul al (K+1)-lea nr. prim ( Ex: k=3, se va afisa 7*7=49).
De asemenea, un prieten mi-a explicat ca el a rezolvat de 100 de pct folosind Ciurul lui Erathostene si inmultire pe numere mari.
Am incercat eu mai multe,am stat ceva timp pr problema,dar..mai mult de 50 pct nu am scos..si asta fara sa folosesc ciuru'... :D
Cum as putea face ?

A..si asta e sursa aia a mea de 50 pct...imi iese din timp pentru celelalte teste ,nu cred ca ajuta la ceva.....

Cod: Selectaţi tot

#include<iostream.h>
#include<fstream.h>
#include<math.h>
ifstream f &#40;"prim.in"&#41;;
ofstream g&#40;"prim.out"&#41;;
int main&#40;&#41;
&#123;
	long long int k,i,j,ok,n,v&#91;100000&#93;;
	f >> k;
	f.close&#40;&#41;;
	n=1;
	cout<<"k="<<k<<endl;
	for &#40;i=1; i<=k+1; i++&#41;
	&#123;
		do
		&#123;
		n=n+1;
		ok=0;
		for &#40;j=2; j<=sqrt&#40;n&#41;; j++&#41;
			if &#40;n%j==0&#41;
				ok=1;
		&#125;
		while &#40;ok==1&#41;;
		v&#91;i&#93;=n;
	&#125;

	g<<v&#91;k+1&#93;*v&#91;k+1&#93;<<" ";
	g.close&#40;&#41;;
&#125;
	
Multumesc ca ai citit atata !!! :D

Blaugranas

Mesaj de Blaugranas » 30 Ian 2011, 14:06

Pai foloseste ciurul. Exista o implementare naiva a lui si una optima...Cred ca si cea naiva ar merge in prb ta. Daca vrei ti-o scriu pe cea naiva...iar daca n-o sa-ti mearga cu ea...iti dau link-ul sau functia care o calculeaza optim, depinde acuma cum vrei. Avand in vdr ca se lucreaza cu nr mari o sa-ti iasa mereu din program. TLE (time limit exceeded). Banuiesc ca ai luat prb de pe infoarena.ro nu? Astept sa-mi zici ce preferi.

noobakaflo
utilizator
utilizator
Mesaje: 34
Membru din: 03 Noi 2010, 21:35

Mesaj de noobakaflo » 13 Feb 2011, 11:25

Multumesc de raspuns, dar am reusit sa o rezolv ! :D

Cod: Selectaţi tot

#include<iostream.h>
#include<fstream.h>
ifstream f&#40;"prim.in"&#41;;
ofstream g&#40;"prim.out"&#41;;

int main&#40;&#41;
&#123;
	long long k,var,nr,i,j,y;
	int sita&#91;2000000&#93;;
	f >> k;
	f.close&#40;&#41;;
	var=k+1;
	for &#40;i=1; i<=2000000; i++&#41;
		sita&#91;i&#93;=1;
	for &#40;i=2; i*i<=2000000; i++&#41;
	if &#40;sita&#91;i&#93;==1&#41;
	&#123;
		j=2; 
		while &#40;i*j<=2000000&#41;
		&#123;
			sita&#91;i*j&#93;=0;
			j++;
		&#125;
	&#125;
	nr=0;
	for &#40;i=2; i<=2000000; i++&#41;
		if&#40;sita&#91;i&#93;==1 && nr<var&#41;
		&#123;
			nr++;
			y=i;
		&#125;
		g<<y*y;
		g.close&#40;&#41;;
&#125;

Scrie răspuns
  • Subiecte similare
    Răspunsuri
    Vizualizări
    Ultimul mesaj