Afiseaza al x-lea numar prim

#include <iostream>
using namespace std;

int x;

int prim(int n)
{
   if(n==1)
   return 0;
   for(int i=2; i*i<=n; i++)
     if(n%i==0) return 0;
   return 1;
}

int main()
{
   int nr=0 i=0;
   cin>>x;
   while(nr<x)
   {
      i++;
      if(prim(i))
         nr++;
   }
   cout << i;
   return 0;
}

Cam asa. E banal... trebuie insa sa mai si citim cate cava. Altfel nu ai cum sa inveti...

E banal, dar nu prea eficient.

 sharp10, on 01 aprilie 2018 - 13:54, said:

solutia ta e buna doar daca te intereseaza strict invatarea limbajului (cuvinte cheie, declararea variabilelor etc). din punctul de vedere al eficientei algoritmului, este cea mai proasta varianta.
uite, ca sa-ti faci o idee despre cat de eficient este: poti dubla viteza de executie inlocuind acel "i++" cu "i+=2" (si avand grija sa inceapa de la 1, nu de la 0). explicatia e simpla: nu are rost sa cauti numere prime pare , deci e suficient sa iterezi printre numerele impare (deci in loc sa verifici daca 1,2,3,4,5,6,7,8... sunt prime, mai bine verifici doar 3,5,7...)

Prietene cel care a cerut programul habar nu are de programare. Cred ca ai remarcat asta. Programul propus e mai mult decat eficient. Ca ai adus tu o mica optimizare prin injumatatirea nr de teste.... nu spune mare lucru. Si apropos, vezi ca 2 e numar prim dupa matematica mea. Tu il excluzi daca "pleci de la 1".
Apoi era o chestie didactica si faptul ca se merge pana la radical din n e aur fata de solutiile vehiculate pe aici cu calculul numarului de divizori etc. Daca vrei optimalitate folosesti ciurul lui Eratostone dar a zis ca nu vrea vectori. Oricum, la procesoarele de azi, o reducere la jumatate a numarului de teste pentru asta e apa de ploaie. Ca sa vezi cat poti duce tu prin inbunatatirea propusa, un int are aproximativ valori pana la circa 32000. Banuiesc ca nu sti de ce dar mai citesti tu... Apoi eu am mers pana la radical din asta, deci pana la vreo 180. Si tu ai eliminat jumatate din teste deci vreo 90. Esti tare rau. Mi-ar fi rusine pentru acea interventie.

A... si inca ceva. Prin modul de implementare(cu acea functie) iesirea pentru nr pare se face imediat dupa testul div cu 2. Restul testelor de divizibilitate nu se mai fac.

Edited by sharp10, 02 April 2018 - 09:09.

"prietene", n-ai inteles nimic din ce am explicat eu
m-am referit la bucla din main, nu cea din functia prim. adica asta:

int main()
{
int nr=0 i=0;
cin>>x;
while(nr<x)
{
	 i++;
	 if(prim(i))
		 nr++;
}
cout << i;
return 0;
}

si crede-ma pe cuvant, nu are rost sa te intrebi daca un numar par este prim . cu mici exceptii (adica pt 2), nu este.
cat despre numarul de teste evitate, nu este 90, ci un pic mai mare. n-am glumit cand am spus ca dublezi viteza, deci din 32.000 teste o sa eviti fix 16.000 teste.

Edited by _Smiley_, 02 April 2018 - 09:37.

K discutia astanu duce nicaieri. Am lucruri mai bune de facut.

Edited by sharp10, 02 April 2018 - 10:08.

Am făcut programul ăsta în python, de amuzament. Practic, testez fiecare număr impar (îl împart la toate numerele până la radical din el însuși (rotunjit +1)). Apoi adaug numerele prime în listă. Când lungimea listei = x, se oprește programul și ultimul număr din listă e cel căutat.

import math

nr_ales = x
# Aici e X-ul cu pricina, trebuie înlocuit cu numărul dorit.
prime_list = [2,3,5,7,]

for nr in range(11,1000000000,2):
# M-am limitat la numerele prime până la un miliard :)
  for test in range(3, 1 + int(math.sqrt(nr))):
	 if nr % test == 0:
		 if prime_list[-1] == nr:
			 del prime_list[-1]
		 break
	 elif nr != prime_list[-1]:
		 prime_list.append(nr)
  if len(prime_list) == nr_ales:
	 break

print(prime_list[-1])

L-am testat până la al 100.000 număr prim, funcționează corect.

Edited by Mr_nobody_, 02 April 2018 - 15:54.

Va certati degeaba. Initiatorul a intrebat si n-a mai dat pe forum.

Da... oricum nu cred ca e locul acetei postari aici. Asta e tema unui elev de clasa a IX-a.😊 dar ne faceam si noi de lucru pe aici.

 Mr_nobody_, on 02 aprilie 2018 - 15:52, said:

Știu că nu interesează pe nimeni...
...dar am reparat o greșeală și am îmbunătățit căutarea prin evitarea împărțirii la numere pare:

import math

nr_ales = int(input("Al catelea numar prim il vrei?\n"))
prime_list = [2,3,5,7,]

for nr in range(11,1000000000,2):
	if nr_ales < 5:
		break
	for test in range(3, 1 + int(math.sqrt(nr)), 2):
		if nr % test == 0:
			if prime_list[-1] == nr:
				del prime_list[-1]
			break
		elif nr != prime_list[-1]:
			prime_list.append(nr)
	if len(prime_list) == nr_ales:
		break

print("Al " + str(nr_ales) + "-lea numar prim e " + str(prime_list[nr_ales -1]) + ".")

# Am adaugat cod care genereaza lista de numere prime pana la numărul ales:
nr_prime = open("nr_prime.txt", "w")
for item in prime_list:
	nr_prime.write(str(item) + "\n")