Zählnummern mit drei verschiedenen Primfaktoren

Question

Es gibt 1000 Zahlen in numbers.txt, jeweils 2 bis 9 Ziffern, jeweils in einer eigenen Zeile. Die Aufgabe ist es zu zählen, wie viele Zahlen es gibt, die die Bedingung erfüllen: wenn sie faktorisiert sind, hat diese Zahl genau 3 verschiedene Primfaktoren, sie können mehrmals auftreten und sie sind alle gerade Zahlen.

beispiel - Faktoren: 3, 5, 7 - JA, - Faktoren: 3, 3, 11, 13 - JA,

- Faktoren: 3, 3,3,5,5,5,7,7,7 - JA,

- Faktoren: 5, 11 - NEIN.

#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; 
} 

Ich weiß aus dem numbers.txt, dass es viele Zahlen sind, die die Bedingung erfüllen, aber das Programm kehrt nur 1. Warum so?

Answer 1

Ihr Code ignoriert die Tatsache, dass 2 eine Primzahl ist. Sie müssen prüfen, ob die Anzahl lesen kann durch 2 reduziert werden Sie mit etwas tun könnte, die wie folgt aussehen:

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 
} 

Diese ganze Sache effizienter gemacht werden könnte, indem eine Liste von Primzahlen machen, die nach oben geht zu der maximalen Anzahl möglich in der Datei, die in diesem Fall 999.999.999 wäre. Dann können Sie einfach durch diese Primzahlliste iterieren, bis Sie keine Primfaktoren mehr haben. Das würde ungefähr so ​​aussehen:

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 
}