计算具有三个不同质因数的数

Question

numbers.txt中有1000个号码，每个号码2到9个数字，每个号码占一行。练习是计算有多少个数满足条件：分解后，这个数恰好有3个不同的质因数，它们可以出现多次，而且都是偶数。

例如 105 - 因子：3、5、7 - 是， 1287 - 因子：3、3、11、13 - 是，

1157625 - 因子：3,3,3,5,5,5,7,7,7 - 是，

55 - 因子：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;
}

我从numbers.txt得知，满足条件的数字有很多，但是程序returns只有1个，为什么？

Answer 1

您的代码忽略了 2 是素数这一事实。您需要检查读入的数字是否可以减少 2。您可以使用如下所示的方法来做到这一点：

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
}

整个事情可以通过制作一个素数列表来提高效率，该列表可以达到文件中可能的最大数量，在本例中为 999,999,999。然后你可以遍历那个素数列表，直到你运行出素数。那看起来像

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
}

计算具有三个不同质因数的数

Counting numbers that have three different prime factors

c++

primes