Подсчитайте общие простые делители двух чисел
Опубликовано: 5 Января, 2022
Учитывая два целых числа 
а также 
, задача состоит в том, чтобы найти количество общих делителей двух чисел, у которых делители простые.
Примеры:
Input: A = 6, B = 12
Output: 2
2 and 3 are the only common prime divisors of 6 and 12
Input: A = 4, B = 8
Output: 1
Наивный подход: выполните итерацию от 1 до min (A, B) и проверьте, является ли i простым и множителем как A, так и B , если да, то увеличьте счетчик.
Эффективный подход заключается в следующем:
- Найдите наибольший общий делитель (НОД) заданных чисел.
- Найдите простые множители НОД.
Ниже представлена реализация описанного выше подхода:
C ++
// CPP program to count common prime factors// of a and b.#include <bits/stdc++.h>using namespace std;// A function to count all prime factors of// a given number xint countPrimeFactors( int x){ int res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i <= sqrt (x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res;}// Count of common prime factorsint countCommonPrimeFactors( int a, int b){ // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd);}// Driver codeint main(){ int a = 6, b = 12; cout << countCommonPrimeFactors(a, b); return 0;} |
Джава
// Java program to count common prime factors // of a and b.import java.io.*;class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0 ) return b; if (b == 0 ) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(ab, b); return __gcd(a, ba); }// A function to count all prime factors of// a given number x static int countPrimeFactors( int x){ int res = 0 ; if (x % 2 == 0 ) { res++; // Print the number of 2s that divide x while (x % 2 == 0 ) x = x / 2 ; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3 ; i <= Math.sqrt(x); i = i + 2 ) { if (x % i == 0 ) { // While i divides x, print i and // divide x res++; while (x % i == 0 ) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2 ) res++; return res;}// Count of common prime factorsstatic int countCommonPrimeFactors( int a, int b){ // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd);}// Driver code public static void main (String[] args) { int a = 6 , b = 12 ; System.out.println(countCommonPrimeFactors(a, b)); }}// This code is contributed by inder_verma.. |
Python3
# Python 3 program to count common prime# factors of a and b.from math import sqrt,gcd# A function to count all prime# factors of a given number xdef countPrimeFactors(x): res = 0 if (x % 2 = = 0 ): res + = 1 # Print the number of 2s that divide x while (x % 2 = = 0 ): x = x / 2 # x must be odd at this point. So we # can skip one element (Note i = i +2) k = int (sqrt(x)) + 1 for i in range ( 3 , k, 2 ): if (x % i = = 0 ): # While i divides x, print i # and divide x res + = 1 while (x % i = = 0 ): x = x / i # This condition is to handle the # case when x is a prime number # greater than 2 if (x > 2 ): res + = 1 return res# Count of common prime factorsdef countCommonPrimeFactors(a, b): # Get the GCD of the given numbers gcd__ = gcd(a, b) # Count prime factors in GCD return countPrimeFactors(gcd__)# Driver codeif __name__ = = '__main__' : a = 6 b = 12 print (countCommonPrimeFactors(a, b)) # This code is contributed by# Surendra_Gangwar |
C #
// C# program to count common prime factors// of a and b.using System ;class GFG { // Recursive function to return gcd of a and b static int __gcd( int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(ab, b); return __gcd(a, ba); } // A function to count all prime factors of // a given number x static int countPrimeFactors( int x) { int res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( int i = 3; i <= Math.Sqrt(x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = x / i; } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors static int countCommonPrimeFactors( int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } // Driver code public static void Main() { int a = 6, b = 12; Console.WriteLine(countCommonPrimeFactors(a, b)); } // This code is contributed by Ryuga} |
PHP
<?php// PHP program to count common// prime factors of a and b.// Recursive function to return// gcd of a and bfunction __gcd( $a , $b ){ // Everything divides 0 if ( $a == 0) return $b ; if ( $b == 0) return $a ; // base case if ( $a == $b ) return $a ; // a is greater if ( $a > $b ) return __gcd(( $a - $b ), $b ); return __gcd( $a , ( $b - $a ));}// A function to count all prime// factors of a given number xfunction countPrimeFactors( $x ){ $res = 0; if ( $x % 2 == 0) { $res ++; // Print the number of 2s that // divide x while ( $x % 2 == 0) $x = $x / 2; } // x must be odd at this point. So we // can skip one element (Note i = i +2) for ( $i = 3; $i <= sqrt( $x ); $i = $i + 2) { if ( $x % $i == 0) { // While i divides x, print i // and divide x $res ++; while ( $x % $i == 0) $x = $x / $i ; } } // This condition is to handle the case // when x is a prime number greater than 2 if ( $x > 2) $res ++; return $res ;}// Count of common prime factorsfunction countCommonPrimeFactors( $a , $b ){ // Get the GCD of the given numbers $gcd = __gcd( $a , $b ); // Count prime factors in GCD return countPrimeFactors( $gcd );}// Driver code$a = 6;$b = 12;echo (countCommonPrimeFactors( $a , $b ));// This code is contributed by akt_mit..?> |
Javascript
<script> // Javascript program to count // common prime factors of a and b. // Recursive function to return // gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(ab, b); return __gcd(a, ba); } // A function to count all prime factors of // a given number x function countPrimeFactors(x) { let res = 0; if (x % 2 == 0) { res++; // Print the number of 2s that divide x while (x % 2 == 0) x = parseInt(x / 2, 10); } // x must be odd at this point. So we // can skip one element (Note i = i +2) for (let i = 3; i <= Math.sqrt(x); i = i + 2) { if (x % i == 0) { // While i divides x, print i and // divide x res++; while (x % i == 0) x = parseInt(x / i, 10); } } // This condition is to handle the case // when x is a prime number greater than 2 if (x > 2) res++; return res; } // Count of common prime factors function countCommonPrimeFactors(a, b) { // Get the GCD of the given numbers let gcd = __gcd(a, b); // Count prime factors in GCD return countPrimeFactors(gcd); } let a = 6, b = 12; document.write(countCommonPrimeFactors(a, b)); </script> |
Выход:
2
Если есть несколько запросов для подсчета общих делителей, мы можем дополнительно оптимизировать приведенный выше код, используя простую факторизацию, используя Sieve O (log n) для нескольких запросов.
Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .