023 Numere Prime

[•SpiderMan]

Iti da TLE pentru ca algoritmul tau nu e eficient, trebuie folosit la problema asta Ciurul lui Eratosthenes.

[•DEYDEY2]

iau 3 TLE-uri... ce as mai putea optimiza?

[•visanr]

Iei 100 daca faci:

Cod:

if(!prim[i])
        {
            nr++;
            if(nr == k + 1) return i;

[•DEYDEY2]

Multumesc!

[•alexandru70]

Se poate uita cineva si peste sursa mea? Iau 70p pe ea, si din cate am reusit eu sa imi dau seama este ca imi sare niste numere prime de la 10000 in sus, si nu pot sa imi dau seama de ce.
http://www.infoarena.ro/job_detail/925090

[•Balescu_Ovidiu]

Se poate uita cineva la sursa mea, scrisa mai jos? Imi da 50 de puncte fiindca la ultimele 5 teste imi iese din timp. Pana acum nu am reusit sa gasesc o solutie sa mearga mai repede.

Cod:

#include<stdio.h>
#include<stdlib.h>
unsigned long k,d,i,q=1,n=3,N; unsigned a[99988]; short flag=1;
int main()
{
    FILE*f=fopen("prim.in","rb"); fscanf(f,"%lu",&k); fclose(f);
    FILE*g=fopen("prim.out","wb");
    if(k>1)
    {
        while(q<k)
        {
            flag=0;
            for(d=3;d*d<=n&&!flag;d+=2)
                if(n%d==0) flag=1;
            if(flag==0)
            {
                q++;
                a[q]=n;
            }
            n+=2;
        }
        N=n;
        while(flag==0)
        {
            n+=2;
            for(d=N;d*d<=n&&!flag;d+=2) if(n%d==0) flag=1;
            if(flag==1) for(i=2;i<=k&&flag;i++) if(n%a[i]==0) flag=0;
        }
        fprintf(g,"%ld",n);
    }
    else fprintf(g,"%d",9);
    fclose(g);
    return 0;
}

[•tudormaxim]

pe ultimele 6 teste iau TLE...am neaparat nevie de optimizare pe biti la ciurul lui erastostene ca sa iua 100?

[•klamathix]

Nu, dar ce ai facut tu acolo nu e ciurul lui Eratosthene. Tu verifici primalitatea lui x in O(x).

http://www.infoarena.ro/problema/ciur

Ai aici detalii despre ciur 

[•sulzandrei]

Am aici   o demonstratie facuta de mine pt. a sustine ca cel mai mic numar neprim nedivizibil prin primele k numere prime e al k+1 numar prim la patrat, nus daca e corecta ce ziceti?  

[•Eberardo]

Da...ce mai demonstratie ai boss..e inversul verificarii daca un numar e prim.
E corect,trebuie afisat al k+1-lea numar prim,ceea ce poti observa din exempli,si daca nu te-ai convins mai iei cateva si observi ca asta-i

[•Dupree7]

Daca introduc valori in prim.in imi da raspunsul corect dar nu inteleg de ce cand il uploadez primesc 0 puncte deoarece toate raspunsurile sunt incorecte. Ma poate ajuta cineva?

Cod:

#define lim 1000000
#include <fstream>
using namespace std;

bool prim [lim];

fstream f("prim.in");
ofstream g("prim.out");

int main()
{
    int i,j,c=0,k;
f>>k;
for(i=2;i<lim;i++)
{
    if(prim[i]==0)
        {
            c++;
    for(j=i*2;j<=lim;j+=i)
       prim[j]=1;
       }
    if(prim[i]==0) if(c==k+1){ g << i*i; return 0;}
}
}

[•Slevy]

Am facut problema initial cu Erastotene si am alocat static un tablou de 1.500.000 de elemente (bool eras[1500000]) si primeam killed by signal 11 pe primele 2 teste si 80p.. apoi am alocat dinamic tabloul eras (bool *eras; eras = new bool[1500000] si am luat 100p. Vreo idee de ce diferenta asta ?? o fi din cauza dimensiunii prea mari a tabloului ??

[•CrystyAngel]

Am observat ca evaluatorul nu accepta din cstdio (cand folosesc fscanf si fprintf) I64d, am luat incorect pe teste si am schimbat in %lld si a dat bine

[•DanielRusu]

Imi poate spune cineva, va rog, cu ce am gresit la bitset?
http://www.infoarena.ro/job_detail/1841098?action=view-source --> Aici am folosit bitset pentru ciur si am luat doar 20 puncte
http://www.infoarena.ro/job_detail/1841105?action=view-source --> Aici am folosit char  pentru ciur si am luat 100 de puncte..
Asta e singura diferenta intre cele doua surse.
Multumesc anticipat!

[•andrei.arnautu]

Cod:

for(long long j = i * i; j <= DIM; j += i) {
                CE[j] = 1;
            }

In codul tau iterezi cu j-ul pana la DIM, ceea ce e gresit, fiindca containerul bitset e indexat de la 0 la DIM - 1, si atunci cand ajungi exact in DIM, accesezi aiurea, ceea ce conduce la greseli. Acelasi lucru il faci si in sursa cu char, dar aparent acolo nu are aceleasi urmari.

[•DanielRusu]

e indexat de la 0 la DIM - 1, si atunci cand ajungi exact in DIM, accesezi aiurea, ceea ce conduce la greseli.

Cat noroc am avut  ..mersi mult 

[•viorel12]

#include <iostream>
using namespace std;
long i=2,k,n=1,ok=1;
long sum(int i)
{
    int j,s=0;
    for(j=1;j<i;j++)
        if(i%j==0)
        s=s+j;
    return s;
}
int main()
{
    cout<<"k=";
    cin>>k;
    while(n<=k)
    {
        if(i==sum(i)+1)
            n++;
        else
            i++;
    }
    cout<<n;
    while(i<=LONG_MAX||ok==1)
    {
     if(n%i==0&&i==sum(i)+1)
        i++;
     else
        ok=0;
    }
    cout<<i;
    return 0;
}
de ce nu merge?

[•alexcojocaru02]

e normal sa am un timp de 0,0000123?

[•alexcojocaru02]

e normal sa am un timp de 0,0000123?