Prüfen, ob eine Zahl gleichmäßig durch viele andere geteilt wird

Question

Ich habe ein Programmierproblem, das mich auf die 30.000 Hexagonale Zahlen überprüfen soll (gegeben durch die Formel: H (n) = n (2n-1)), wie viele davon teilbar sind durch die Zahlen 1 bis 12

I-Code haben wie folgt:

#include <iostream> 
#include <cstring> 

using namespace std; 

int main() 
{ 
    int hex, count = 0; 

    for (int n = 1; n <= 30000; n++) 
    { 
     hex = n * ((2 * n) - 1); 

     if (hex % 1 == 0 && hex % 2 == 0 && hex % 3 == 0 && hex % 4 == 0 && hex % 5 == 0 && hex % 6 == 0 && hex % 7 == 0 && hex % 8 == 0 && hex % 9 == 0 && hex % 10 == 0 && hex % 11 == 0 && hex % 12 == 0) 
     { 
      count++; 
     } 
    } 

    cout << count << endl; 
} 

jetzt weiß ich den Scheck habe ich jetzt in meiner if-Anweisung sehr ineffizient ist, so dass ich frage mich, ob es eine einfachere Möglichkeit, die Nummer zu überprüfen? Ich habe versucht, eine for-Schleife zu verwenden, aber konnte es nicht zum Laufen bringen (da es nur 1 Zahl auf einmal prüft). Irgendwelche Ideen?

Answer 1

Wenn a[i] | x für 1 <= i <= n, dann lcm(a[1], ..., a[n]) | x

Für diesen Fall müssen nur wenn lcm(1,2,...,12) | h überprüfen, das heißt h % 27720 == 0

---

1. https://en.wikipedia.org/wiki/Least_common_multiple

Answer 2

können Sie einfach eine andere Verwendung für Schleife, um von der langen if-Anweisung loszukommen dass du benutzt hast.

#include <iostream> 
#include <cstring> 

using namespace std; 

int main(){ 
    int hex, count = 0; 
    int divider = 12; 

    for (int n = 1; n <= 30000; n++){ 
     hex = n * ((2 * n) - 1); 

     int subcount = 0; 
     for (int i = 1; i <= divider; ++i){ 
      if (hex % i == 0){ 
       ++subcount; 
       if(subcount == devider){ 
        ++count; 
       } 
      } 
     } 
    } 

    cout << count << endl; 
}