CODEWITHSUNDEEP
c++primes
Sebastian
Sebastian

Reputation: 1305

Counting numbers that have three different prime factors

There are 1000 numbers in numbers.txt, 2 to 9 digits each, each in a seperate line. The exercise is tocount how many numbers there are, that fullfill the condition: when factorized, this number has exactly 3 different prime factors, they can occur several times and they all are even numbers.

for example 105 - factors: 3, 5 ,7 - YES, 1287 - factors: 3, 3, 11, 13 - YES,

1157625 - factors: 3,3,3,5,5,5,7,7,7 - YES,

55 - factors: 5, 11 - NO.

#include <iostream>
#include <fstream>
using namespace std;
int number, threefnumbers=0;
int main()
{
  ifstream file("numbers.txt");
  ofstream outputf("results.txt");
  int count_factors;
  while (file >> number)
  {
    count_factors=0;
    int factor=3;
    if (number%2!=0)
    {
       while (number>1)
       {
        if (number%factor==0)
          count_factors++;
        while (number%factor==0)
        {
          number=number/factor;
        }
        factor+=2;
       }
       if (count_factors==3) threefnumbers++;
     }
  }

  outputf << "59.1) " << endl << threefnumbers;

  file.close();
  outputf.close();
  return 0;
}

I know from the numbers.txt, that there are many numbers that fulfill the condition, but the program returns only 1. Why so?

Upvotes: 3

Views: 216

Answers (1)

NathanOliver
NathanOliver

Reputation: 180945

Your code ignores the fact that 2 is a prime number. You need to check if the number read in can be reduced by 2. You could do that with something that look like:

while(read number)
{
    int factor_count = 0;
    // check 2 by itself
    if (number % 2 == 0)
    {
        factor_count++;
        while(number % 2 == 0)
            number /= 2;
    }
    for (int factor = 3; factor < number; factor += 2)
    {
        if (number % factor == 0)
        {
            factor_count++;
            while(number % factor == 0)
                number /= factor;
        }
    }
    if(factor_count == 3)
        do something
}

This entire thing could be made more efficient by making a list of prime numbers that goes up to the max number possible in the file which in this case would be 999,999,999. Then you can just iterate through that prime number list until you run out of prime factors. That would look something like

std::vector<int> primes = get_prime_list(999999999);  
// returns a list of all prime numbers less than the number passed in.
// leaving it to you to implement but a Sieve of Eratosthenes should work well
while(read number)
{
    int factor_count = 0;
    for(auto e : primes)
    {
        if (number % e == 0)
        {
            factor_count++;
            while(number % e == 0)
                number /= e;
        }
        if (number == 1) // number is fully factorized
            break;
    }
    if(factor_count == 3)
        do something
}

Upvotes: 2

Related Questions