Segmented Sieve Spoj

Question

I tried(trying...) to solve the SPOJ prime number problem PRIME1 so i learned and implemented Segmented Sieve correctly but this program works in time for 10^8 but getting Time limit exceeded (TLE) for 10^9 input integer. can someone help me reduce complexity within my code please.

/*
 followed this tutorial
 https://medium.com/@agilanbtdw/prime-number-generation-in-java-using-segmented-sieve-of-eratosthenes-187af1dcd051
*/
#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>
using std::cin;
using std::ifstream;
using std::vector;
using std::cout;
using std::ios_base;
int main() {
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
    //ifstream in("inp.txt");
  short int t;
  unsigned long int n ,q;
  cin >> t; 
  while(t--){
  cin >>q >> n;
  vector<bool> a(n,true);
  unsigned long int m = sqrt(n); 
  a[0] = false;
  a[1] = false;
  // find primes till sqrt
  for(unsigned long int i = 2 ; i <= m ; i++ ){
    if(a[i]){
      for(unsigned long int j = i*i ; j <= m ; j+=i ){
        a[j] = false;
      }
    }
  }
//  store the primes upto m
  vector<unsigned long int> primes;
  for(unsigned long int i = 2 ; i <= m ; i++ ){
      if(a[i]){ primes.push_back(i);}
  }

  unsigned long int temp;
  for (unsigned long int x : primes) {
        temp = q/x;
        temp*=x;
                // from primes arrays increment each prime with that num , set the index as false
        for(unsigned long int y = temp ; y <=n ; y+=x){
        a[y] = false;
        }
  }
// set the falsed indexes in previous primes arrays to true
  for(unsigned long int i = 0 ; i < primes.size() ;++i){
    a[primes[i]] = true;
  }
  for(unsigned long int i =q ; i <= n ; i++ ){
    if(a[i]) {cout << i << " ";}
  }
  cout << "\n";
  }
  return 0;
}

my repl link - https://repl.it/repls/UnrulyMotherlyTransformation

Answer 1

Reducing Complexity
The first thing to do for reduced complexity is to break up the code into multiple functions. This would allow you to profile the code and see where it spends the most time. This also makes it easier to read, write and debug the code. There are possibly 5 functions in main. As programs get more complex it is generally better to limit the main() function to set up and clean up and do all other processing in sub functions.

This would be applying the Single Responsibility Principle to the code which is the first pillar of SOLID object oriented programming. The Single Responsibility Principle states The single responsibility principle is a computer programming principle that states that every module, class, or function[1] should have responsibility over a single part of the functionality provided by the software ...

Variable Names
Generally single character variable names make code harder to read and debug. It is unclear what the variables t, n, q or m are or do.

Use Explict Casts
The line of code

unsigned long int m = sqrt(n);

is an implicit cast and generates warning messages in some compilers. C++ attempts to be type safe and casts should be explict, in this particular case it would be better to use a static_case.

Performance
It looks like this code checks all numbers in a range, there is no reason to process even numbers except for 2 since all even numbers greater than 2 can't be prime numbers because they are divisible by 2.

Indentation
The code is improperly indented immediately after the while statement. This makes it much harder to read the code.

Answer 2

following the advice to make the main function smaller and outsource (quite literally) as much as possible in seperate functions i came up with this:

// spoj.cpp: Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h" //vc++ specific may be ommitted

#include <iostream>
#include <math.h>
#include <vector>
#include <fstream>

#include <stdint.h>

using std::cin;
using std::cout;
using std::ifstream;
using std::vector;
using std::ios_base;

void findPrimesUponTillSqrtN(uint64_t sqrtN, vector<bool> * Flag)
{       
    for (register uint64_t i = 2; i <= sqrtN; i++) 
    {
        if ((*Flag)[i]) 
        {
            for (register uint64_t j = i * i; j <= sqrtN; j += i) 
            {
                (*Flag)[j] = false;
            }
        }
    }
}

void storePrimesUponTillSqrtN(uint64_t sqrtOfN, vector<uint64_t> * primes, vector<bool> * Flag)
{
    for (register uint64_t i = 2; i <= sqrtOfN; i++) 
    {
        if ((*Flag)[i]) 
        {
            (*primes).push_back(i); 
        }
    }
}
void primesManipulation(vector<uint64_t> * primes, vector<bool> * Flag,uint64_t n, uint64_t q)
{
    for (uint64_t x : (*primes)) 
    {
        uint64_t temp;
        temp = q / x;
        temp *= x;
        // from primes arrays increment each prime with that num , set the index as false
        for (register uint64_t y = temp; y <= n; y += x) 
        {
            (*Flag)[y] = false;
        }
    }
}

void flagMultiplesOfFoundPrimes(vector<bool> * Flag, vector<uint64_t> * primes)
{
    // set the falsed indexes in previous primes arrays to true
    register const uint64_t sizeOfPrimes = (*primes).size();
    for (register uint64_t i = 0; i < sizeOfPrimes; ++i) 
    {
        (*Flag)[(*primes)[i]] = true;
    }
}

void printFoundPrimes(uint64_t q, uint64_t n, vector<bool> * Flag)
{
    for (register uint64_t i = q; i <= n; i++) 
    {
        if ((*Flag)[i])
        {
            cout << i << " "; 
        }
    }
    cout << "\n";
}
void sieve(int64_t t, uint64_t q, uint64_t n)
{
    while (t--) 
    {
        cin >> q >> n;
        vector<bool> Flag(n, true);
        Flag[0] = false;
        Flag[1] = false;
        uint64_t sqrtOfN = sqrt(n);

        findPrimesUponTillSqrtN(sqrtOfN,&Flag); 

        vector<uint64_t> primes;
        storePrimesUponTillSqrtN(sqrtOfN, &primes, &Flag);

        primesManipulation(&primes, &Flag, n, q);

        flagMultiplesOfFoundPrimes(&Flag, &primes);

        printFoundPrimes(q, n, &Flag);
    }
}

int main() 
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    //ifstream in("inp.txt");
    int64_t t;
    uint64_t n, q;
    cin >> t;
    sieve(t, q, n);
    return 0;
}

explaination / thoughts / Input / Food for thought:

1. renamed Array/vector a to Flag (according to the link given in your Code)
2. changed type of just About everything to uint64_t this is what modern x64 processors should be optimized for and if Nothing else it does save you some keystrokes in the Long run.
3. often used variables get the Register qualifier to state that this variable is intended to be stored in a Register. the Compiler may or may not place them in Registers but if he does it Speeds up your Code significantly.
4. as i dont know of top if vectors are passed to functions as pointers per Default i pass over a pointer to them to ensure that. Maybe this is not at all necessary.
5. naming convention: it does not cost you anything (not even Computational power) to give variables and functions meaningful names. this helps others (like me, who had a hard time figuring out the meaning of your variables) to grasp your algorithm faster and makes some comments completely unneccessary
6. using sqrt Returns a double and you store that in an integer variable of some sort!!! this is at best horrible style there is an sqrtl function available!!!
7. your temp variable is only used inside that one Codeblock that can easily refactored in a new function so making it local instead may bring some Advantages...
8. temp = q/x; temp*= x; yields q if q/x is not fractional… and therefor this can surely be optimized
9. the lenght of your primes Vector is constant (or at least it is for the time you call your for loop that flags all the multiples of found primes) therefor there is no Need to retrieve that Information over and over again. store it in a variable declare it constant and tell the Compiler to store it in Registers if he is in the mood to do so.
10. some Parameters that are asked for during the runtime like the Limits are not neccessarily to be asked there. they can be given at the time the Program is called using commandline paramameters for instance. this may reduce runtime a Little bit because the whole cin Thing has not to be executed.
11. further improvements may result from not using cout or printf or the like and immediately print to stdout without traversing the same dozen layers of abstraction everytime.
12. vectors as such may be slow as they allow to add and remove Elements and therefor are basically variable lenght Arrays. internally they are most likely not more than linked lists which are known for their slowness and thus should be avoided.