c++ - What is Happening to my Sieve of Eratosthenes Program? -
i'm trying solve challenge question of summing primes under 2 million. knowing full naive approach take long, decided implement sieve of eratosthenes counter record sum. works 512500 after receive error:
is input size big code handle? if that's case, how can improve code avoid error. if that's not possible, better algorithm implement these purposes?
here header code:
#ifndef numbersieve_h #define numbersieve_h class numbersieve { public: numbersieve(); virtual ~numbersieve(); int eratosthenessieve(int num); private: void setsieve(int nums[],int size); int current_prime; int current_prime_address; void updatesieve(int nums[],int size,int start); bool updatecurrentprime(int nums[],int size,int start); bool notcomplete; void printsieve(int nums[],int size); int primesum; }; #endif // numbersieve_h here implementation file:
#include "numbersieve.h" #include <cstdlib> #include <iostream> numbersieve::numbersieve() { //ctor } numbersieve::~numbersieve() { //dtor } void numbersieve::setsieve(int nums[],int size) { for(int i=0;i<size;i++) { nums[i]=(i+1); } nums[0]=0;//sets first composite number 1 0. use 0 analogy "crossing out numbers in sieve". } void numbersieve::updatesieve(int nums[],int size,int start) { int current_prime=nums[start]; for(int i=start;i<size;i++) { if(nums[i]%current_prime==0) { nums[i]=0; } } nums[start]=current_prime; } bool numbersieve::updatecurrentprime(int nums[],int size,int start) { for(int i=start+1;i<size;i++) { if(nums[i]!=0) { primesum+=nums[i]; current_prime=nums[i]; current_prime_address=i; return true; } } return false; } void numbersieve::printsieve(int nums[],int size) { for(int i=0;i<size;i++) { std::cout<<nums[i]<<std::endl; } } int numbersieve::eratosthenessieve(int num) { int eratosthenes[num]; int primesum=0; setsieve(eratosthenes,num); current_prime=2; primesum+=2; current_prime_address=1; updatesieve(eratosthenes,num,current_prime_address); notcomplete=updatecurrentprime(eratosthenes,num,current_prime_address); while(notcomplete) { updatesieve(eratosthenes,num,current_prime_address); notcomplete=updatecurrentprime(eratosthenes,num,current_prime_address); } return primesum; }
my best guess stackoverflow, because of this:
int eratosthenes[num]; instead try getting free store:
int* eratosthenes = new int[num] update rest of code accordingly
if not comfortable pointers, vector might option.
Comments
Post a Comment