Hello. Requesting help with the prime1 problem. I used a segmented sieve so the max array size should be max((n - m), sqrt(n)) which I double checked by printing sizeof(array) to standard output. However I am still getting a sigsegv runtime error when m and n in the range are very large values. If anyone has some insight as to where in the program the memory limit is being exceeded that would be very helpful. And sorry for the messy/inefficient code.
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
using std::vector;
vector<int> simple_sieve(int);
vector<int> seg_sieve(int, int, vector<int>);
struct Range{
Range(int x, int y):range_start(x), range_end(y) { }
int range_start, range_end;
};
int main(){
// Read how many ranges the user requests
int range_quant;
std::cin >> range_quant;
// Read and save all the given ranges in a vector
vector<Range> range_val_collection;
int start_range_val = 0, end_range_val = 0;
for(int i = 0; i < range_quant; i++){
std::cin >> start_range_val >> end_range_val;
if(0 <= start_range_val <= end_range_val){
range_val_collection.push_back(Range(start_range_val, end_range_val));
}
}
// Iterate through vector of ranges and print primes for each one
for(vector<Range>::const_iterator iter = range_val_collection.begin(); iter != range_val_collection.end(); iter++){
int start, end;
vector<int> small_primes;
vector<int> primes;
start = iter->range_start;
end = iter->range_end;
int limit = floor(sqrt(end));
small_primes = simple_sieve(limit);
primes = seg_sieve(start, end, small_primes);
for(vector<int>::const_iterator iter = primes.begin(); iter != primes.end(); iter++){
std::cout << *iter << "\n";
}
std::cout << "\n";
}
return 0;
}
// Returns a vector of primes between [1, end] where end is the sqrt(range_end)
vector<int> simple_sieve(int end){
bool is_composite[end + 1] = { false };
vector<int> primes;
// std::cout << "limit: " << end << "\n";
// std::cout << "simple sieve memory: " << sizeof(is_composite) << "\n";
for(int factor = 2; factor <= end; factor++){
for(int multiple = factor; multiple < (end + 1); multiple += factor){
if((multiple == factor) && (is_composite[factor] == false)){
// std::cout << "Is prime: " << multiple << "\n";
is_composite[multiple] = false;
} else {
// std::cout << "Is multiple: " << multiple << "\n";
is_composite[multiple] = true;
}
}
}
for(int i = 2; i < (end + 1); i++){
if(!is_composite[i]){
primes.push_back(i);
}
}
return primes;
}
// Returns a vector of primes between [start, end]
vector<int> seg_sieve(int start, int end, vector<int> base_factors){
bool is_composite[end - start] = { false };
vector<int> primes;
// std::cout << "range: " << (end - start) << " segmented sieve memory: " << sizeof(is_composite) << " array size: " << (sizeof(is_composite)/sizeof(is_composite[0])) << "\n";
for(vector<int>::const_iterator iter = base_factors.begin(); iter != base_factors.end(); iter++){
// std::cout << "Is base prime: " << *iter << "\n";
for(int multiple = *iter; multiple <= end; multiple += *iter){
if((multiple == *iter) && (is_composite[*iter - start] == false)){
is_composite[multiple - start] = false;
// std::cout << "Is prime: " << multiple << "\n";
} else {
is_composite[multiple - start] = true;
// std::cout << "Is multiple: " << multiple << "\n";
}
}
}
for(int i = 0; i <= (end - start); i++){
if((!is_composite[i]) && ((start + i) != 0) && ((start + i) != 1)){
// std::cout << "Is prime: " << i + start << "\n";
primes.push_back(i + start);
}
}
return primes;
}