023 Numere Prime

[•xtreme]

fii atent sa faci ciurul pana la 1.500.000 intrucat cel de-al 100.000-lea nr prim e undeva la 1.300.000
si restul intra in long long (n-ul)
bafta

am fakut ciurul de 2000000 nu pot sa inteleg ce nu merge...este n-u mai mare ca si 2000000?

[•Mishu91]

Eu am facut ciurul pana la 3 milioane, dar nu cred ca poate atinge mai mult de 2 milioane, dupa cum zicea in postul de mai sus

[•c_e_manu]

ai grija cum faci ciurul...mai cauta si alte greseli... insa daca faci corect 2 000 000 e mai mult decat suficient...

[•xtreme]

cat ar trebui sa imi dea pentru k=100.000?
am fakut cu ciurul in 2 moduri diferite si tot 20 de puncte

Cod:

#include<iostream.h>    
#include<fstream.h>

int main()
    {
     unsigned char v[2000000];long int i,j,k,nrprime=0;  
     fstream f("prim.in",ios::in),g("prim.out",ios::out);  
     f>>k;  
     for(i=1;i<=2000000;i++)  
              v[i]='0';  
     for(i=2;i<=2000000;i++)  
              if(v[i]=='0')  
                     {  
                     if(nrprime!=k)  
                            {  
                            nrprime++;  
                            for(j=i+i;j<=2000000;j+=i)  
                                       v[j]='2';  
                            }  
                      else     
                             for(j=i+i;j<=2000000;j+=i)  
                                        if(v[j]=='0')    
                                               v[j]='1';  
                      }  
     for(i=2;i<=2000000;i++)  
              if(v[i]=='1')  
                           {g<<i;break;}  
     f.close();g.close();  
     return 0;  
     }  
[\code]       
                           
 

[•Mishu91]

De ce marchezi si cu 1 si cu 2? 

[•xtreme]

De ce marchezi si cu 1 si cu 2? 

cu '0' nr prime cu '2' divizorii primelor k nr prime si cu '1' divizorii restu nr. prime

[•c_e_manu]

1689274677841 imi da mie...

http://infoarena.ro/job_detail/161860?action=view-source eu de obicei asa implementez ciurul... asa am facut si la problema asta si a mers... merge si cum ai facut tu... dar nu inteleg sensul sa marchezi si cu 2

1689243484681 iti da cumva tie?

[•xtreme]

1689274677841 imi da mie...

http://infoarena.ro/job_detail/161860?action=view-source eu de obicei asa implementez ciurul... asa am facut si la problema asta si a mers... merge si cum ai facut tu... dar nu inteleg sensul sa marchezi si cu 2

1689243484681 iti da cumva tie?

nu imi da atat.....nu kred ka e buna ideea mea....eu am crezut ca daka marchez in vectoru de 2 milioane cu '0' nr prime si cu '2' divizori primelor k nr prime si cu '1' restu...e evident ca indicele care e cel mai mic si care in v de indice contine '1' acela e nr cautat
 

[•c_e_manu]

ai pe paginile astea un indiciu foarte important despre care este numarul cautat... e al (k+1)-lea numar prim la patrat.. credeam ca tu afisezi al k-lea numar prim la patrat...

asa problema se reduce sa faci ciurul si sa cauti al k-lea numar prim

[•xtreme]

ai pe paginile astea un indiciu foarte important despre care este numarul cautat... e al (k+1)-lea numar prim la patrat.. credeam ca tu afisezi al k-lea numar prim la patrat...

asa problema se reduce sa faci ciurul si sa cauti al k-lea numar prim

.
mersi,mi-am dat seama atunci cand mi-ai zis rezultatul pentru k=100000

[•catalin93]

De ce marchezi si cu 1 si cu 2? 

cu '0' nr prime cu '2' divizorii primelor k nr prime si cu '1' divizorii restu nr. prime

de ce nu iti faci un vector de bool si fiecare numar compus (neprim) il marchezi cu true... si astfel fiind initializat global pe false ai numere prime
mie asa mi se pare cel mai simplu

[•shnako]

Imi puteti spune careva de ce iau Wrong answer pe ultimele 5 teste ? Am mai facut un program si al 100 000lea numar prim dadea undeva sub 1 300 000 deci aia e ok.

Cod:

#include <stdio.h>
#include <math.h>
long k, i, n=1300000, x;
bool v[1300000];
void prim(void)
{
for (i=3;i<=n;i=i+2)
	v[i]=1;
for (i=3;i<=sqrt(n);i=i+2)
   for (register long t=i;t*i<=n;t++)
   	v[i*t]=0;
}
int find(long k)
{
long t=1;
for (register int i=3;i<=n;i++)
	if (v[i])
      {
   	t++;
      if (t==k+1)
      	return i;
      }
}
int main(void)   

{
freopen("prim.in", "r", stdin);
freopen("prim.out", "w", stdout);
scanf("%ld", &k);
prim();
x=find(k);
printf("%ld", x*x);
fcloseall();
return 0;
}

P.S.: E ceva in neregula cu declaratia long long int k, i, n=1300000, x; ? Ca daca incerc sa le declar asa imi spune Too many types in declaration.
La fel imi spune si daca nu mai scriu int, doar long long.

[•c_e_manu]

Cod:

printf("%lld", x*x);

si declara-le long long... eu am declarat chiar unsigned long long pentru orice eventualitate, atunci cand am facut problema...

[•toni2007]

La mine pe g++ 4.3 de linux, aproximativ la fel cu cel de pe infoarena care e 4.2.3, programul tau compileaza si cu long long. Tu compilezi cumva cu Borland? Borland-ul nu e standard, si nu accepta long long, de aceea crede probabil ca e o eroare la tine.

[•shnako]

L-am trimis cu toate ca Borlandu zicea ca am eroare Am luat 100 de puncte, mersi . Daca am ajuns sa nu mearga programu din cauza lui Borland inseamna ca am inghitit destul . Care ziceti ca e cel mai bun editor/compilator ? Si eventual un link pentru el  Thanks

[•gabitzish1]

http://infoarena.ro/schimbare-borland/pachet

[•c_e_manu]

eu votez cu rhide
http://infoarena.ro/djgpp-instalarea-de-la-a-la-z

[•toni2007]

@emanuel

DJGPP este mult mai vechi, deci si mai indepartat standardului decat MINGW. Nu de putine ori unele programe care compilau cu DJGPP nu compilau cu gcc pe linux, si invers, fapt care mergea cu MINGW. De asemenea, RHIDE, desi este mai asemanator Borland-ului, are mult mai multe buguri, si chiar sa intampla sa crape cu totul, fara sa iti salveze sursa, MINGW Studio sau Dev-Cpp nefacand asta.


Eu personal l-as sfatui pe Vlad sa foloseasca Code Blocks, un mediu de altfel folosit si testat cu succes de mine in ultimii aproximativ 2 ani, atat pe windows cat si pe linux, neavand absolut nici o problema cu el. Compilatorul poate fi setat individual, putand sa compileze chiar si cu Borland, iar editorul este foarte flexibil, poti schimba aproape orice la el, poti seta comenzi de compilare, de rulare, etc, lucruri care nu se pot face in MINGW Developer Studio.

Este alegerea ta ce vrei sa folosesti

[•pauldb]

Incercati sa ramaneti la subiect. Sunt destule topicuri pe forum unde se discuta despre editoare/compilatoare.

[•dushmi]

am incercat sa pregenerez primele 100000 de nr prime... dar nu pot sa trimit programul pentru ca are cam 670 KB si maximul admis e 256 :O...

[•c_e_manu]

am incercat sa pregenerez primele 100000 de nr prime... dar nu pot sa trimit programul pentru ca are cam 670 KB si maximul admis e 256 :O...

nu merge fiindca nu se rezolva astfel... incearca sa-ti invingi lenea si citeste threadul acesta...

[•LowArmour]

Pentru sursa de mai jos imi da la ultimele 5 teste : Killed by signal 11(SIGSEGV).
Unde este problema?
PS: am folosit numarul 1318699 pt ca este al 100 000 numar prim.

Cod:

#include <stdio.h>
char iprim [1318699];
int k;
long int x;
void citire ()
	{
	scanf("%d",&k);}
void prim (int k)
	{
	long int i,j;
	int nr=0;
	for(i=2;i<=1318699;i++)
	    if(nr<k){
		 if(!iprim[i ]){
			      x=i;
			      ++nr;
			      for(j=i*i;j<=1318699;j+=i)
							iprim[j]=1;}}
		 else break;
	}
int main ()
{
freopen ("prim.in", "r", stdin);
freopen ("prim.out", "w", stdout);
citire();
prim(k+1);
printf("%ld", x*x);
return 0;}

Foloseste tag-ul [ code ] !

[•pauldb]

Rezultatul este de tip long long.

Nu mai posta cod ca sa-ti caute lumea greselile. Testeaza-ti singur.

[•LowArmour]

Ok am inteles. Dar ma gandeam ca daca aflu acum care e greseala, pe viitor cand va aparea aceeasi eroare voi sti ce sa fac.
De testat... l-am testat mai mult timp decat l-am conceput... sunt unele greseli care nu ai cum sa le aflii singur. .
Am corectat acum si vad ca imi da aceeasi eroare, in fine voi incerca din nou sa vad daca pot sa rezolv.
Multumesc.

[•wefgef]

Sunt 3 erori in sursa ta:

• Vectorul tau trebuie declarat de marime 1318700, deoarece in C daca aloci un array de dimnesiune N poti accesa elemente cu indicii cuprinsi intre 0 si N-1.
• Rezultatul afisat trebuie sa fie de tipul long long - poti sa faci un cast la printare: printf("%lld\n", ((long long)x) * x);
• In forul in care marchezi multiplii unui numar prim nu trebuie sa incepi de la i*i deoarece aceasta valoare iese din int. E de ajuns sa pornesti de la i