problema c++
-
- Junior
- Posts: 27
- Joined: 11 Aug 2011, 23:12
- Judet: Olt
problema c++
Salut.
Am gasit o problema si anume : sa se calculeze suma numerelor prime mai mici decat 2.000.000.
Personal, nu cred ca se rezolva prin metoda clasica s+=s+i, de exemplu, unde i numar prim;
N-am nicio idee. Cateva sfaturi daca se poate ?
multumesc.
Am gasit o problema si anume : sa se calculeze suma numerelor prime mai mici decat 2.000.000.
Personal, nu cred ca se rezolva prin metoda clasica s+=s+i, de exemplu, unde i numar prim;
N-am nicio idee. Cateva sfaturi daca se poate ?
multumesc.
Re: problema c++
Pai, metoda clasica e o rezolvare si deci e valida. Acum metoda clasica pentru mine e sa le calculezi pe taote si sa le aduni 
Bineinteles ca apoi putem sa ne gandim si la solutii mai eficiente
)
De exemplue calculeaza numerele prime si pune-le intr-un fisier...sau mai bun pune 2.000.000 de sume intr-un fisier

Bineinteles ca apoi putem sa ne gandim si la solutii mai eficiente

De exemplue calculeaza numerele prime si pune-le intr-un fisier...sau mai bun pune 2.000.000 de sume intr-un fisier

Cu stima,
Lupu Claudiu
Lupu Claudiu
Re: problema c++
Code: Select all
#include <list>
#include <stdlib.h>
#include <iostream>
#include <math.h>
class calcprim
{
public:
calcprim(int limit)
{
m_suma = 0;
for(int i=1; i<=limit; ++i)
if(prim(i))
m_suma += i;
std::cout << "suma=" << m_suma << std::endl;
}
private:
bool prim(int n)
{
int max = (int)ceil(sqrt((double)n));
for(std::list<int>::iterator it = m_gasite.begin(); it != m_gasite.end(); ++it)
{
int nr = *it;
if(nr == 1) continue;
if(nr > max)
{
m_gasite.push_back(n);
return true;
}
if(n%nr == 0) return false;
}//
m_gasite.push_back(n);
return true;
}
std::list<int> m_gasite;
unsigned long m_suma;
};
int main()
{
calcprim obj(2000000);
return 0;
}
Caut profesor.
Re: problema c++
Bun, dar...cate numere pare crezi ca sunt? Intreb pentru ca inca nu s-a gasit altul inafara de 2
++i, i+=2?

Cu stima,
Lupu Claudiu
Lupu Claudiu
- cristianamarie
- Membru++
- Posts: 480
- Joined: 12 Mar 2009, 18:47
- Judet: Iaşi
- Location: Iasi
Re: problema c++
Code: Select all
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
struct prime_list_t {
long n;
struct prime_list_t *next;
};
void add_prime_list_t(struct prime_list_t** list, long n);
void free_prime_list_t(struct prime_list_t** list);
long count_prime_list_t(struct prime_list_t* list);
long last_prime_list_t(struct prime_list_t* list);
/* if one of the primes in list divides n, is not a prime */
int is_prime(struct prime_list_t* pl, long n) {
struct prime_list_t* p;
if(pl == NULL) {
abort();
}
p = pl;
while(p != NULL) {
if(n % p->n == 0) {
return 1;
}
p = p->next;
}
return 0;
}
int main() {
struct prime_list_t* pl = NULL;
struct prime_list_t* p;
long n_up = 2000000;
long long p_sum = 0;
long ppr;
int done;
/* add first prime number */
add_prime_list_t(&pl, 2);
/* from now on add to this list up to the number of items */
done = 0;
do {
/* get the last prime plus one */
ppr = last_prime_list_t(pl) + 1;
while(is_prime(pl, ppr) != 0) {
ppr++;
if(ppr >= n_up) {
/* hit the upper limit */
done = 1;
break;
}
}
if(done) {
break;
}
/* ppr is prime */
add_prime_list_t(&pl, ppr);
/* display status */
printf("%ld numbers largest prime %ld\r", count_prime_list_t(pl), last_prime_list_t(pl));
} while(!done);
p = pl;
p_sum = 0;
while(p) {
// printf("%d ", p->n);
p_sum += p->n;
p = p->next;
}
printf("\nsum: %I64d\n", p_sum);
free_prime_list_t(&pl);
return 0;
}
void add_prime_list_t(struct prime_list_t** list, long n) {
struct prime_list_t* node;
if(list == NULL) {
abort();
}
node = (struct prime_list_t*)malloc(sizeof(struct prime_list_t));
if(node == NULL) {
abort();
}
node->n = n;
node->next = NULL;
if(*list == NULL) {
*list = node;
}
else {
struct prime_list_t* p;
p = *list;
while(p->next != NULL) {
p = p->next;
}
p->next = node;
}
}
void free_prime_list_t(struct prime_list_t** list) {
struct prime_list_t* node;
if(list == NULL) {
return;
}
node = *list;
while(node != NULL) {
struct prime_list_t* p;
p = node;
node = node->next;
free(p);
}
*list = NULL;
}
long count_prime_list_t(struct prime_list_t* list) {
long c;
struct prime_list_t* p;
for(p = list, c = 0; p != NULL; p = p->next, c++)
;
return c;
}
long last_prime_list_t(struct prime_list_t* list) {
long n;
struct prime_list_t* p;
n = 0;
p = list;
while(p->next != NULL) {
p = p->next;
}
return p->n;
}
Code: Select all
$kpwr
148933 numbers largest prime 1999993
sum: 142913828922
$
Nuclear launch detected
- cristianamarie
- Membru++
- Posts: 480
- Joined: 12 Mar 2009, 18:47
- Judet: Iaşi
- Location: Iasi
Re: problema c++
Cristi, @bu7ch3r zicea sa-l pui si pe 3 in lista
add_prime_list_t(&pl, 2);
add_prime_list_t(&pl, 3);
si dupa sa mergi din 2 in 2:
ppr = last_prime_list_t(pl) + 2;
Apreciez .c -ul de mai sus. Great.
add_prime_list_t(&pl, 2);
add_prime_list_t(&pl, 3);
si dupa sa mergi din 2 in 2:
ppr = last_prime_list_t(pl) + 2;
Apreciez .c -ul de mai sus. Great.
Caut profesor.
- cristianamarie
- Membru++
- Posts: 480
- Joined: 12 Mar 2009, 18:47
- Judet: Iaşi
- Location: Iasi
Re: problema c++
comment-ul lui era dinaintea codului meu... n-am facut legaturamihk wrote:Cristi, @bu7ch3r zicea sa-l pui si pe 3 in lista
add_prime_list_t(&pl, 2);
add_prime_list_t(&pl, 3);
si dupa sa mergi din 2 in 2:
ppr = last_prime_list_t(pl) + 2;
Apreciez .c -ul de mai sus. Great.

Nuclear launch detected
- cristianamarie
- Membru++
- Posts: 480
- Joined: 12 Mar 2009, 18:47
- Judet: Iaşi
- Location: Iasi
Re: problema c++
sum: 142913828922
bu7ch3r wrote:Da cat dureaza sa faceti suma ?
Nuclear launch detected
Re: problema c++
[mihk@myhost otcc]$ uname -a
Linux myhost 3.1.8-1-ARCH #1 SMP PREEMPT Sat Jan 7 08:03:08 UTC 2012 i686 Intel(R) Core(TM)2 Duo CPU T7700 @ 2.40GHz GenuineIntel GNU/Linux
[mihk@myhost otcc]$ time ./nrprim
sum: 1179908154
real 2m41.860s
user 2m37.910s
sys 0m0.127s
E compilat cu TCC deci probabil sa nu fie super optimizat. Initial am incercat cu OTCC dar am uitat ca nu suporta pointeri.
OS-ul e in vmware.
Si stii ceva, chiar si rezultatul e diferit. As fi rulat pe un telefon, dar la ce am eu, nici bateria nu tine mai multe de 10 poze.
Linux myhost 3.1.8-1-ARCH #1 SMP PREEMPT Sat Jan 7 08:03:08 UTC 2012 i686 Intel(R) Core(TM)2 Duo CPU T7700 @ 2.40GHz GenuineIntel GNU/Linux
[mihk@myhost otcc]$ time ./nrprim
sum: 1179908154
real 2m41.860s
user 2m37.910s
sys 0m0.127s
E compilat cu TCC deci probabil sa nu fie super optimizat. Initial am incercat cu OTCC dar am uitat ca nu suporta pointeri.
OS-ul e in vmware.
Si stii ceva, chiar si rezultatul e diferit. As fi rulat pe un telefon, dar la ce am eu, nici bateria nu tine mai multe de 10 poze.
Caut profesor.
Re: problema c++
Eu am mai putine....
pt 10000 am 1229 si suma 5736396 asta e verificat cel putin 1229 de numere sunt acum nu cred sa fi gresit la suma
) dar dupa 10 mii nu bag mana in foc
pt 2 mil am 148 909 si suma 1155307852
141 de miliarde diferenta e ceva
)
3 oameni 3 rezultate. Testez acum ce am facut initial cu varianta cea mai ciobanizata care vad ca merge de ceva vreme
) si va zic ce mi-a dat si mie.
La mine pe o racla: pentium M la 1.7 cu 1 giga de ram sub 1 secunda pe release(instant adik)
pt 10000 am 1229 si suma 5736396 asta e verificat cel putin 1229 de numere sunt acum nu cred sa fi gresit la suma

pt 2 mil am 148 909 si suma 1155307852


3 oameni 3 rezultate. Testez acum ce am facut initial cu varianta cea mai ciobanizata care vad ca merge de ceva vreme

La mine pe o racla: pentium M la 1.7 cu 1 giga de ram sub 1 secunda pe release(instant adik)

Cu stima,
Lupu Claudiu
Lupu Claudiu
Re: problema c++
Dupa lupte seculare care au durat 30 de minute, cu tot cu fumat 
Avem:
Mai este o metoda, moosaby sau wasabi sau nush ce si mai este si AKS
? Dar nu mi-am mai batut capul, mai sunt oricum. Nici cu "sita"(sieve inseamna sita nu fac eu pe interesantul
) ) nu as iesi in lume ca e cel mai rapid, dar cu siguranta e printre cele mai rapide;) si...nu e metoda clasica dar e metoda antica (era sita lui Erastotene):)
Acum, iar, un drac de clasa a 5-a ne bate la algoritmi.Eu stiu sigur ca am auzit in gimnaziu de sita lui Erastotene dar am fost indoctrinat din clasa a 9-a cu for de la 1 la sqrt
)

Avem:
Code: Select all
#include "stdafx.h"
#include <vector>
#include "math.h"
using namespace std; //neaparat std ca asa sunt programele in c++ / std::size_t
std::vector<bool>sieve(2000000, true);//global asa vreau eu sa fie tot frumos aliniat pe stack :)
std::vector<int>primes;
std::vector<int>otherprimes;//cred ca am uitat de namespace :P
int suma_prime( size_t n )
{
int suma = 0;
size_t sieveSize = sieve.size();//2 mil ha ha :p
for(size_t i = 2; i < sieveSize; i++)
if(sieve.at(i)) //daca gasim un prim ii omoram toti multipli apoi il luam pe urmatorul si tot asa
for(size_t j = i+i; j < sieveSize; j += i)//si tot asa ca de aia e bucla :)
sieve.at(j) = false ;
for(size_t i = 2; i < sieve.size(); i++)
if(sieve.at(i))
{
suma += i;
primes.push_back(i);
}
return suma;
}
int otherprime()
{
long long suma = 5;
otherprimes.push_back(2);
otherprimes.push_back(3);
int counter = 2;
for(int i = 5; i<=2000000;i=i+2)
{
bool prim = true;
int stop = (int)sqrt((long double)i);
if(i%1000 == 0)
printf("\n1000");//DESTEPT NU ? :))
for(int div = 3; div <= stop; div++)
{
if(i % div == 0)
{
prim = false;
break;
}
}
if(prim)
{
suma+=i;
counter++;
otherprimes.push_back(i);
}
}
printf("\n%ld", suma);
printf("\n%ld", counter);
return 1;
}
size_t _tmain(size_t argc, _TCHAR* argv[])
{
size_t suma = suma_prime(2000000);
printf("\n%d", suma);
printf("\n%d", primes.size());
getchar();
otherprime();
getchar();
return 0;
}


Acum, iar, un drac de clasa a 5-a ne bate la algoritmi.Eu stiu sigur ca am auzit in gimnaziu de sita lui Erastotene dar am fost indoctrinat din clasa a 9-a cu for de la 1 la sqrt

Cu stima,
Lupu Claudiu
Lupu Claudiu