Подсчет чисел, которые имеют три разных простых коэффициента

Question

В числителе имеется 1000 номеров. От 2 до 9 цифр каждый по отдельности. Упражнение состоит в том, чтобы подсчитать количество чисел, которые заполняют условие: при факторизации это число имеет ровно 3 разных простых фактора, они могут возникать несколько раз, и все они являются четными числами.

, например - факторы: 3, 5, 7 - ДА, - факторы: 3, 3, 11, 13 - ДА,

- факторы: 3, 3,3,5,5,5,7,7,7 - ДА,

- Факторы: 5, 11 - НЕТ.

#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, что есть много чисел, которые удовлетворяют условие, но программа возвращает только 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 
}