023 Numere Prime

[•LowArmour]

Multumesc. Am rezolvat.

[•valentinrosca]

Aici merge __int64

[•gabitzish1]

Nu. Foloseste long long in loc de __int64.

[•valentinrosca]

Mi-am dat seama.

Raspunsu este al k+1 numar prim la patrat.
I-mi iese 50 de puncte.
Nu-mi iese la numere mari.
Ma poate ajuta cineva la chestia asta.Va rog! [...]
Eu lucrez in C++.
[..]
Pls!
Va rog!
[...]

[editat de moderator] Nu mai posta consecutiv si fii sigur ca daca folosesti multe smiley-uri nu vei fi ajutat prompt!

[•sima_cotizo]

Incearca sa faci debug sau fii mai exact cand spui ca nu-ti iese.

[•vlad_oltean]

ajutati-ma si pe mine, va rog frumos. am o problema foarte dubioasa. am facut problema, merge corect si pe testul cu 100.000, dar imi afiseaza gresit
stiu sigur ca algoritmul e bun, pentru ca in debug imi apare valoarea corecta, dar in fisierul de iesire e o aberatie. mai precis, am codul urmator:

Cod:

#include <stdio.h>
#define N 1318700

bool prim[N];
long long x;
int count,k;

int main()
{
	freopen("prim.in","r",stdin);
	freopen("prim.out","w",stdout);
	
	scanf("%d",&k);
	[...]
	for(...)
		if(...)
		{	x=i*i;
			printf("%lld",x);
			break;
		}
	}	
	fclose(stdin); fclose(stdout);
	return 0;
}

exact asta fac. e foarte dubios, pentru ca daca dau 100000, in debug imi arata x ca fiind 1.689.274.677.841, iar in fisierul de iesire, in urma instructiunii printf("%lld",x) imi afiseaza 1.352.530.513. ce gresesc?

[•c_e_manu]

Folosesti cumva Borland? Eventual incearca si cu streamuri sau "%I64" (aici s-ar putea sa ma insel, ca nu am folosit niciodata ) in loc de "%lld".

[•gh09]

vine "%I64d". Dar totusi pe infoarena trimie cu "%lld" pt ca se testeaza pe linux!

[•vlad_oltean]

  am luat suta cu fstream. as fi recunoscator daca mi-ar explica cineva de ce.
nu folosesc borland, folosesc mingw studio. din cate am inteles ar trebui sa se comporte la fel cu compilatorul de pe infoarena.

[Edit]
foarte foarte aiurea... cu "%I64d" ala iau doar 50..

[Later edit]
eu nu mai inteleg absolut nimic.. deci cu fstream e ok si la mine si pe site, dar mi-e mie incomod. cu stdio imi da mie bine daca folosesc "%I64d", dar da gresit pe site. daca folosesc "%lld", imi da gresit pe compilatorul meu, dar corect in evaluator. e aiurea rau de tot

[•c_e_manu]

Pe MinGW e un mic bug despre care s-a mai vorbit pe infoarena la afisarea unui "long long" folosind printf(). Eu mai nou folosesc streamuri fiindca au devenit mai rapide. Doar in concursuri in care se folosesc compilatoare mai vechi folosesc printf() si scanf(). Plus ca imi e mai usor sa scriu un fout<<var decat printf("%d",var).

[•vlad_oltean]

fout>>var

  semnele nu se pun invers (<<) din cate stiu eu? e clar cat iti e de usor...

[•sima_cotizo]

[Later edit]
eu nu mai inteleg absolut nimic.. deci cu fstream e ok si la mine si pe site, dar mi-e mie incomod. cu stdio imi da mie bine daca folosesc "%I64d", dar da gresit pe site. daca folosesc "%lld", imi da gresit pe compilatorul meu, dar corect in evaluator. e aiurea rau de tot

Este o diferenta intre MinGW si g++ la afisarea numerelor long long. Pe g++ se foloseste %lld; pe MinGW, I64d. Cum pe infoarena se compileaza cu g++, iata de ce iei bine aici si gresit la tine cand afisezi cu lld.

Fstream se descurca la fel si pe MinGW si pe g++ si de-aia e ok in ambele parti.

[•vlad_oltean]

Este o diferenta intre MinGW si g++ la afisarea numerelor long long. Pe g++ se foloseste %lld; pe MinGW, I64d. Cum pe infoarena se compileaza cu g++, iata de ce iei bine aici si gresit la tine cand afisezi cu lld.

Fstream se descurca la fel si pe MinGW si pe g++ si de-aia e ok in ambele parti.

multumesc pentru clarificare asta inseamna ca e cazul sa-mi schimb compilatorul cu unul mai asemanator cu g++?

[•c_e_manu]

fout>>var

  semnele nu se pun invers (<<) din cate stiu eu? e clar cat iti e de usor...

My bad  

[•sima_cotizo]

multumesc pentru clarificare asta inseamna ca e cazul sa-mi schimb compilatorul cu unul mai asemanator cu g++?

Nu neaparat. Daca ai in vedere diferenta asta, atunci poti sa folosesti MinGW in continuare (care e foarte asemanator cu g++ oricum). Poti sa incerci si Visual Studio Express care mi se pare ca afiseaza tot cu lld...

[•valentinrosca]

Pai am facut un program de 90 pt si la ultmul test imi iese din timp
si nu stiu testul.Dar o sa rezolv chestia asta

[•miculprogramator]

Salut ! Am citit tot topicul si am gasit informatii folositoare legate de problema. Am incercat sa fac intocmai: pun intr-un vector x toate numerele prime pana la 5.000.000 apoi afisez  (x[K+1]*x[K+1]). Numai ca imi da 1, am facut afisare anumerelor din vector si este buna. Cred ca problema mea ar fi la ciur pentru ca afisarea am facut-o astfel:

Cod:

 for(int i=2;i<=max;i++) 
if(x[i]==1) std::cout<<i<<' ';

Asa ca am incercat

Cod:

(x[K+1+2])*(x[K+1+2])

pentru ca eu incep i-ul de la 2. Insa tot nu merge.

Unde ar putea fi problema? 

[•marcelcodrea]

Din ce am inteles eu, tu in vectorul x ai ciurul si nu sirul de numere prime(ai si numere neprime acolo).
Tu prin (x[K+1]*x[K+1]) nu ridici la patrat al (K+1)-lea numar prim ci al (K+1)-lea numar.  Tu trebuie sa iterezi prin vectorul x si sa numeri cate de (x[it] == 1) ai (cate numere prime ai) cu o variabila aux, si doar cand aux pe care o numeri astfel, e egala cu k+1 trebuie sa afisezi x[it] * x[it] unde it e valoarea iteratorului.

[•miculprogramator]

Am descoperit ce greseam era la ciur ! Am reusit, mersi . 

Edit: Am observat niste gresel in enuntul problemei:

Demonstreaza ca ideea lui Ghoerghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N care nu este divizibil cu primele K numele prime, dar nu este prim.

Nu-i o observatie rautacioasa, vreau doar sa atrag atenita asupra acestor greseli minore. 

[•pauldb]

Am rezolvat. Este bine ca semnalati astfel de erori! 

[•vladtarniceru]

salut tuturor.as avea o problema in legatura cu problema .la programul meu se blocheaza,am facut cu ciurul lui erastostene dar nu-mi merge(se blocheaza cand dau pe execute).ma poate ajuta cineva?va rog mult!!!uite sursa mea:

Cod:

#include<stdio.h>
 int a[10000],x[10000000],i,j,k,l=0,z,dk;
 int q=0;
 FILE *f,*g;
 int ciur(){
     for(i=1;i<=1000000;i++)
         a[i]=0;
     i=2;
     dk=k;
     while(i<=1000){
         if(a[i]==0) 
             for(j=i+i;j<=1000000;j+=i)a[j]=1;
         i++;
     }
     j=1;
     for(i=1;dk>0;i++) if(a[i]==0) {dk--;x[j++]=i;}
 }
  int main(){
      f=freopen("prim.in","rt",stdin);
      g=freopen("prim.out","wt",stdout);
      printf("%d",k);
      ciur();
      q=2;
      while(l==0){
         z=1; 
         while(a[q]==0) q++;
         while(q%x[z]==0 && z<=k) z++;
         l=(z==k);
         q++;
      }
      fprintf(g,"%d",q);
      fclose(g);
      return 0;
  }

daca isi da cineva seama unde e eroarea sa scrie pe forum sau pe id-ul meu vladtarniceru(sau sa mi-o trimita mail la [email protected]).

[•Florian]

Tu nu citesti k-ul (  printf("%d",k); ). a[] e prea mic declarat. Fa si tu un debug ( cu watch, sau cu afisari ). Nu cred ca e indicat sa postezi pe forum chiar orice problema. In curand o sa discutam aici erori de compilare. Nu cred ca asta e scopul infoarena. Spor!  

[•SpiderMan]

Deci nu pot sa cred de ce imi da la ciur aiurea: al 100.000-lea nr. prim zice ca e 1299709 ce am putut gresi? Ciurul l-am facut in 2 moduri si tot asa

[•klamathix]

Pai..ala e. Probabil n-ai folosit long long pentru rezultat.

[•SpiderMan]

Cod:

#define MAX 1500000
bool v[MAX];
long long p[MAX]

Crezi ca e gresit ?