using namespace std;
It won't matter much with this program, but this can be a bad habit to start. See Why is using namespace std bad practice?
Sieve of Eratosthenes
bool f[100000001];
void siv()
You're asking for a code review, so you want to encourage people to read your code. You could make it easier on us by picking self-commenting names. For example, I think these would be more recognizable as
const int MAXIMUM_VALUE = 100000001;
bool is_not_prime[MAXIMUM_VALUE];
void sieve_of_erastothenes()
Now I can easily see what the upper bound is, what is_not_prime holds, and know what the function does. I can also reuse MAXIMUM_VALUE and if I type it incorrectly, I'll get a compiler error. If I miscount the zeroes in 100000001, it will just silently do the wrong thing.
for (long long i = 2; i * i <= 100000001; ++i)
{
if (!f[i])
for (long long j = i * i; j <= 100000001; j += i)
You do i * i twice. You could save it the first time and avoid that.
for ( long long i = 2, j = i * i; j < MAXIMUM_VALUE; ++i, j = i * i )
{
if ( ! f[i] )
{
for ( ; j < MAXIMUM_VALUE; j += i )
{
Not much of an improvement but some. Although the compiler might do this for you already.
Note that I also changed j <= to j <. This prevents us from writing past the end of the array. The array is 0-indexed, so its maximum index is one less than its size.
Even better might be
int *prime_factor_counts = NULL;
void sieve_of_erastothenes(const size_t maximum_value) {
prime_factor_counts = calloc(maximum_value+1, sizeof(int));
if ( NULL == prime_factor_counts )
{
std::cerr << "Failed to allocate array." << std::endl;
exit(EXIT_FAILURE):
}
prime_factor_counts[1] = 1;
for ( size_t i = 2; i*i <= maximum_value; ++i )
{
if ( ! prime_factor_counts[i] )
{
for ( size_t j = i; j <= maximum_value; j += i )
{
++prime_factor_counts[j];
}
}
}
}
Switching from prime_factor_counts[j] = 1 to ++prime_factor_counts[j]; is about the same work but saves additional information. Now we have a record of the count of the prime factors of each number. Note that we are doing more work now (since j starts at i rather than i * i), but it's work that we probably needed to do anyway.
I dropped long long in favor of size_t. The reason is that we can't create an array with more than size_t elements. So there's no point in creating an index variable of any other type.
In C++, elements are undefined unless you specifically set them. That was a bug in your original program. It's fixed here by using calloc which explicitly zero-initializes the memory it allocates.
main
I'm going to simplify main a bit.
int main()
{
int input_row_count;
std::cin >> input_row_count;
std::cout << process_input(input_row_count, 1, 2);
}
This gets most of the logic outside main. We only get the number of rows of inputs directly. Everything else comes through the process_input function.
Technically speaking, we should probably check for an input error. However, if you're willing to live with the consequences of not checking, then I'm not going to insist.
process_input
std::string process_input(int input_remaining_count, int iteration_count, size_t maximum_value)
{
if ( 0 >= input_remaining_count )
{
sieve_of_eratosthenes(maximum_value);
return;
}
size_t start, end, desired_factor_count;
std::cin << start << end << desired_factor_count;
if ( maximum_value < end )
{
maximum_value = end;
}
std::string output = process_input(input_remaining_count - 1, iteration_count + 1, maximum_value);
size_t count = count_matching_numbers(start, end, desired_factor_count);
std::ostringstream out;
out << "Case #" << iteration_count << ": " << count << '\n' << output;
return out.str();
}
The big point to this is to find the maximum value for which we need a factor count before running the sieve_of_eratosthenes. This way we don't have to always calculate a large number.
The second point is that this allows us to only calculate factor counts once across the entire input. The other way, we had to recalculate the factor counts once for each range. This puts the calculation work entirely in the sieve_of_eratosthenes function which had to do most of it anyway.
The original algorithm was probably better for short ranges with high start and end values. It also used less space, since it just saved whether or not a number was prime and the prime factors of a particular number. I don't know if the space increase matters or not given your usage.
count_prime_factors
size_t count_matching_numbers(size_t start, size_t end, size_t desired_factor_count)
{
size_t count = 0;
for ( size_t i = start; i < end; i++ )
{
if ( prime_factor_counts[i] == desired_factor_count )
{
++count;
}
}
return count;
}
Other issues with original
vector<long long>V;
It's pretty common to use ALL_CAPS to mean a constant. This is not a constant, so it might be better named prime_factors.
for(long long q = 1; q <= i; ++q)
{
But later you say
if (V[0] == 1)
V.erase(V.begin());
It would be easier to replace both statements with just
for ( size_t j = 2; j <= i; ++j )
{
Now there's no chance of adding 1 to the vector, so you'll never need to remove it.
I'm also unclear on why the variable is named q. The more common inner loop index variable would be j.
if(i % q == 0)
{
if (!f[q])
V.push_back(q);
}
It may be better if you did the checks in the reverse order.
if (!f[q])
{
if(i % q == 0)
V.push_back(q);
}
Checking if a value is zero should be simpler than checking if the remainder from a division is zero. Of course, the pointer arithmetic may mess that up. It may be worth timing both ways.
vector<long long>V;
V.clear();
V.push_back(q);
if (V.size() == c)
{
++count;
}
Since you only ever check the size of the vector, you don't actually need it. You could replace it with just a counter variable:
size_t prime_factor_count;
prime_factor_count = 0;
++prime_factor_count;
if ( prime_factor_count == c )
{
++count;
}
OOP
I didn't try to change things, but instead of making prime_factor_counts a global variable, you could have made it an object variable. Then both count_matching_numbers and sieve_of_eratosthenes could have been object methods. You could even make prime_factor_counts and sieve_of_eratosthenes static so as to share them across multiple objects. As it is, this code is rather procedural. Why use C++ to write C?
