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:
- renamed Array/vector
a
to Flag
(according to the link given in your Code)
- 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.
- 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.
- 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.
- 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
- 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!!!
- 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...
temp = q/x; temp*= x;
yields q if q/x is not fractional… and therefor this can surely be optimized
- 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.
- 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.
- 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.
- 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.