problema c++

[mircea2011]

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.

[bu7ch3r]

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

[mihk]

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;
}

[bu7ch3r]

Bun, dar...cate numere pare crezi ca sunt? Intreb pentru ca inca nu s-a gasit altul inafara de 2 ++i, i+=2?

[cristianamarie]

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;
}

Mie mi-o zis la urma asa:

Code: Select all

$kpwr
148933 numbers largest prime 1999993
sum: 142913828922

$

Sper ca am socotit bine si n-am gresit vun printf, ceva.

[bu7ch3r]

Eu vorbesc la pereti

[cristianamarie]

adica?

[mihk]

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.

[cristianamarie]

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.

comment-ul lui era dinaintea codului meu... n-am facut legatura

[bu7ch3r]

Da cat dureaza sa faceti suma ?

[cristianamarie]

sum: 142913828922

Da cat dureaza sa faceti suma ?

[mihk]

[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.

[bu7ch3r]

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)

[bu7ch3r]

148933 si 1179908154

[bu7ch3r]

Dupa lupte seculare care au durat 30 de minute, cu tot cu fumat
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;
}

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 )