[Programare]Numere prime 1

[Hertz]

Un numar prim se divide doar cu 1 si cu el insusi.

Primele numere prime : 2 3 5 7 11 13 17 ...

Cate numere prime mai mici ca 1.000.000 au suma cifrelor egala cu 14?

[begood]

#include <iostream.h>

#include <math.h>

int sumac(unsigned long a)

{int n=0;

while(a){a/=10;n++;}

return n;

}

int prim(unsigned long p)

{for(unsigned long i=3;i<=sqrt(p);i+=2)

if(!(p%i)) return 0;

return 1;

}

void main()

{unsigned long n=0;

for(unsigned long i=3;i<1000000;i+=2)

if(prim(i) && sumac(i)==14)

n++;

cout<<n;

}

//netestat.

//i=3 n=0

mie nu-mi numara niciun nr prim, so rezultatul presupun ca e 0. pot spune ca e ciudat.

Hertz, tu ai pus intentionat acel numar 14 ?

LE: LOL, am facut in loc de suma cifrelor, numarul de cifre.

...

int sumac(unsigned long a)

{int n=0;

while(a){n+=a%10;a/=10;}

return n;

}

//rezultat = 1218

[loki]

voiai sa zici 1229?

aaa cate am postat degeaba credeam ca zici ca-i prim

Edited December 3, 2009 by loki

[Hertz]

E corect,bravo begood.

[tw8]

Desi corect, codul lui begood este destul de incet: 8.5 secunde imi ia mie pe un Pentium M @ 1600 MHz.

O solutie mult mai rapida este folosirea unui ciur pentru generarea numerelor prime la inceput. Astfel, se obtine un timp de rulare de 0.04 secunde - de 200 si ceva de ori mai rapid ca cel de mai sus .

Cam asa ar arata codul:

#include <iostream>
#define eprim !NP
#define DIM 1000000
bool NP[DIM];
using namespace std;

void ciur()
{
for(int i=3;i<DIM;i+=2)
	if(eprim[i])for(int j=2*i;j<DIM;j+=i)NP[j]=1;
}

bool e14(int nr)
{
int c=14;
while(nr&&c>=0)c-=nr%10,nr/=10;
return !c; 
}

int main()
{
ciur();
int c=0;
for(int i=3;i<DIM;i+=2)
	if(eprim[i]&&e14(i))c++;
cout<<c;
}

L.E.: Am uitat sa specific. Se pot elimina foarte multe cazuri daca ne gandim ca numerele divizibile cu 3 nu trebuiesc luate in calcul, pentru ca suma cifrelor lor nu poate fi 14 .