Afiseaza al x-lea numar prim

Se dă un număr x. Se cere să se afișeze al x-lea număr prim.
Date de intrare
Se citește la tastatură numărul x.
Date de ieșire
Programul va afișa pe ecran al x-lea număr prim.
Pentru x=4 afiseaza 7;deci se incepe cu numerele prime de la 2.
P.S. Programul sa fie realizat fara vector.

Pseudocod:
creezi o  functie checkPrime(int x) care returneaza true sau false.

in main :

int x; //citeste de la tastatura
for(int i =2; i<=cat_vrei_tu;i++){
if(checkPrime(i)){
j++;
if(j==x){
print i
}
}
}

y=0;//cand y va fi egal cu x programul se opreste
nr=2;

while(y<x)
{
divizori=0;

for(i=1;i<=nr;i++)
if(nr%i==0)divizori++;

if(divizori==2)//nr este numar prim
  y++;

nr++;
}

printf(nr-1);

Edited by getmorefun, 27 October 2017 - 21:30.

https://godbolt.org/g/ygFf1Y dupa adaptarea codului de aici: https://stackoverflo...at-compile-time

Nu cere de la tastatura si nu afiseaza pe ecran. Tu pui in sursa numarul, iar compilatorul il scrie direct in executabil.

Edited by dani.user, 27 October 2017 - 22:24.

wtf, e problema de clasa a 9a.

 dani.user, on 27 octombrie 2017 - 22:08, said:

Ce se intampla de la aproximativ 500 incolo?

Nu se intampla nimic in mod special.
La ce te referi?

https://en.wikipedia...f_prime_numbers

Edited by MarianG, 28 October 2017 - 00:49.

Pentru al 400-lea sa zicem, codul in assembly obtinut este:

main:
  mov eax, 2741
  ret

Pentru getPrime(500):

isPrimeLoop(int, int):
  mov edx, esi
  mov eax, 1
  imul edx, esi
  cmp edi, edx
  jl .L1
.L4:
  mov eax, edi
  cdq
  idiv esi
  test edx, edx
  jne .L10
  xor eax, eax
.L1:
  rep ret
.L10:
  add esi, 1
  mov eax, esi
  imul eax, esi
  cmp eax, edi
  jle .L4
  mov eax, 1
  ret
main:
  push r14
  mov r14d, 5
  push r13
  mov r13d, 6
  push r12
  mov r12d, -1431655765
  push rbp
  mov ebp, 499
  push rbx
  mov ebx, 3
.L12:
  sub ebp, 1
  je .L37
.L15:
  add ebx, 1
  test bl, 1
  je .L15
  cmp ebx, 8
  jle .L12
  mov eax, ebx
  mul r12d
  shr edx
  lea eax, [rdx+rdx*2]
  cmp ebx, eax
  je .L15
  cmp ebx, 15
  jle .L12
  test bl, 3
  je .L15
  cmp ebx, 24
  jle .L12
  mov eax, ebx
  cdq
  idiv r14d
  test edx, edx
  je .L15
  cmp ebx, 35
  jle .L12
  mov eax, ebx
  cdq
  idiv r13d
  test edx, edx
  je .L15
  mov esi, 7
  mov edi, ebx
  call isPrimeLoop(int, int)
  test al, al
  jne .L12
  jmp .L15
.L37:
  mov eax, ebx
  pop rbx
  pop rbp
  pop r12
  pop r13
  pop r14
  ret

Compilatorul are o limita pentru evaluarea constexpr. Se poate mari cu -fconstexpr-depth=

 getmorefun, on 27 octombrie 2017 - 21:30, said:

Mersi ,nu mi-a mai furnizat eroare acum!]

Edited by dorian2001, 28 October 2017 - 09:34.

for(i=1;i<=nr;i++)
if(nr%i==0)divizori++;

aoleu, asa se verifica in ziua de azi daca un numar e prim? Va bate matematica tare.

nu stiu daca mai e nevoie,dar va arat si eu o versiune pascal,e o problema destul de des intalnita si poate mai au si altii nevoie de ea

var i,k,j,x:integer;
	 p:byte;
begin
read(x);
i:=1;
k:=2;
while i<=x do
	 begin
		 p:=0;
		 for j:=1 to k do if k mod j=0 then p:=1;
		 if p=0 then
			 begin
				 i:=i+1;
				 k:=k+1
			 end
		 else k:=k+1;
	 end;
write(k);
end.
	

Edited by salcudean99, 29 October 2017 - 19:14.

Ca să știți și voi: divizorii se verifică până la sqrt (n)

 getmorefun, on 27 octombrie 2017 - 21:30, said:

Buna, imi poate explica cineva acest cod, ca la prosti? Sunt nou in programare. In mare parte cred ca am inteles, ce nu reusesc sa inteleg care este treaba cu acel nr = 2 , nr -1 , in principiu variabila nr, ce reprezinta, care este scopul ei si cum functioneaza

Un numar prim are doi divizori, { 1, n }
Daca se gasesc mai multi atunci nu este prim.

 mstmst, on 22 martie 2018 - 21:26, said:

Hello, mai jos ai varianta mai buna pentru tine:

#include <iostream>
#include <string>
using namespace std;
int main(){
int numar = 17;
int divizori = 0;
	for (int i = 1 ; i<= numar; i++) {
		if (numar % i == 0 ) { //am gasit un divizor 
			if(++divizori > 2) { //daca nr divizorilor este mai mare ca 2
			 cout<< "nu este prim";  
			 return 0;
			}
		}
	}
cout<<"este prim";
return  0;   
}

cateva observatii:
-n-are rost sa va incalciti in subtilitati de genul "1 si n sunt divizori" sau "nr>2". verificati de la inceput intervalul corect (de la 2 pana la n-1), codul o sa fie mult mai clar
-a mai spus cineva, dar fara sa explice: daca X este divizor al lui N, atunci exista Y astfel incat N = X*Y. practic asta inseamna ca nu-i nevoie sa cautati tot intervalul (1, n), ci doar (1, sqrt(n)], unde sqrt(n) = radical din n. asta deoarece in intervalul ( sqrt(n), n) veti gasi doar valorile Y, pe care le-ati fi putut deduce deja atunci cand ati gasit X-ul aferent.
-multi ati rezolvat de fapt o alta problema: se cere al X-lea numar prim, nu sa se spuna daca un numar este prim sau nu


problema problemei din acest topic este ce optimizari se cer. daca singura restrictie este sa nu se foloseasca vectori, atunci cea mai simpla solutie este cea iterativa: pornesti de la I = 1 si-l incrementezi, apoi verifici daca este nr prim. daca este atunci decrementezi X. cand ai ajuns cu X la 0 te opresti, iar in I o sa ai al X-lea nr prim.
problema acestei variante este ca implica un numar foarte mare de calcule, iar pentru valori maricele ale lui X algoritmul o sa dureze o gramada.
varianta "corecta", foarte rapida, implica o gramada de matematica. in principiu se foloseste algoritmul Meissel–Lehmer pt a determina pi(x) ( https://en.wikipedia...ehmer_algorithm ). cu functia pi(x) se poate determina un interval foarte mic in care poate fi gasit al X-lea numar prim.

Daca ar intra in aria in care trebuie ar gasi si un grafic pentru

Quote