Funkcja sprawdzająca, czy dwie liczby mają te same dzielniki pierwsze

Miałem napisać funkcję sprawdzającą, czy dwie liczby mają te same dzielniki pierwsze. Czy funkcja poniżej jest ok, czy możaby coś poprawić, żeby szybciej działała?

int a(int m, int n)
{
int i;
	for (i=2; i<=m; i++)
	{
		if(m%i==0)
		{
			if(n%i!=0) return 0;
			else
			{
				while (m%i==0) m=m/i;
				while (n%i==0) n=n/i;
			}
		}}
			if(n>=2) return 0;
			else return 1;
}

Ta funkcja zwróci true dla 4 i 8, których faktoryzacja to odpowiednio {2, 2} i {2, 2, 2} - na pewno o to chodzi? Jeśli tak, to szukanie wygląda ok, ale warunki przy wartościach zwracanych są dziwne.

Czy chodzi Ci o to, żeby sprawdzić czy mają dwa (co najmniej dwa?) dzielniki będące takimi samymi liczbami pierwszymi? Bo jak tak to nie.

' Napisz funkcję, która sprawdzi, czy dwie mają te same dzielniki pierwsze' Np. dla par 2,64 oraz 63,147 funkcja powinna zwrócić 1,a dla par 10,12 oraz 18,27 wartość 0 '

To jak tak to mocno nie tak, Najpierw trzeba sprawdzić parę "przypadków granicznych", a potem, po prostu sprawdzać dzielniki pierwsze, jak znajdziemy dzielący tylko jedną z liczb, to return 0, a w przeciwnym przypadku 1.

#include <iostream>
#include <cmath>

using namespace std;

int is_same_prime_factors(unsigned int m, unsigned int n);
int is_prime(int n);
int main (){
	cout << is_same_prime_factors(63, 147) << endl; // -> 1	
	cout << is_same_prime_factors(15, 75) << endl;	// -> 1
	cout << is_same_prime_factors(1, 1) << endl;	// -> 0
	cout << is_same_prime_factors(10, 12) << endl;	// -> 0
	cout << is_same_prime_factors(25, 35) << endl;	// -> 0
	return 0;
}

int is_same_prime_factors(unsigned int m, unsigned int n){
	int limit;
	if (n == 1 || m == 1) return 0;
	if (n == m) return 1;
	if (is_prime(n) && is_prime(m)) return 0;
	if (n < m) limit = n / 2; else limit = m / 2;  
	for (int i = 3; i < limit + 1; i += 2){
		if (is_prime(i)){
			if ( (n % i == 0 && m % i != 0) ) return 0;
			else if ( (n % i != 0 && m % i == 0) ) return 0;
			else if ( (n % i == 0 && m % i == 0) ) continue;
		}
	}
	return 1;
}

int is_prime(int n){
	if (n <= 3) {return n > 1;}
	else if (n % 2 == 0 || n % 3 == 0) {return 0;}
	
	else{
		for (int i = 5; i <= sqrt(n); i = i + 2){
			if (n % i == 0) return 0;
		}
		return 1;
	} 
}

Cały czas uważam, że moja funkcja jest ok:

1. Szukam pierwszego dzielnika pierwszego liczby m - jakieś 'p', jeśli n nie dzieli się przez p od razu zwracam 0.
2. Dzielę obydwie liczby przez p tak długo, żeby już nie dzieliły się przez tą liczbę pierwszą
3. Szukam kolejnych dzielników liczby m, to wykonuje się tak długo, aż dzielniki się skończą
4. Jeżeli n ma jeszcze jakieś dzielniki, czyli jeżeli wartość n jest równa co najmniej 2 to znaczy, że ma jakiś dzielnik pierwszy, którego nie ma 'm' - zwracam wartość 0, w przeciwnym wypadku 1

Np. dla 63 i 147:
2 nie dzieli 63
3 dzieli 63, dzieli też 147
63:2=21, 21:2=7, m=7
147:3=49, n=49
4 nie dzieli 7
5 nie dzieli 7
6 nie dzieli 7
7 dzieli 7, dzieli też 49
7:7=1 m=1
49:7=7, 7:7=1, n=1
m=1 więc koniec pętli for
n=1, więc te same dzielniki pierwsze

Prawdę powiedziawszy, tak, można sporo poprawić aby funkcja działała szybciej, w szczególności można wykorzystać pomysł podobny do tego występującego w algorytmie Euklidesa. Czas jaki udało mi się uzyskać ciężko mi wyliczyć dokładnie, natomiast mogę go ograniczyć z góry poprzez O(log^2(x)), gdzie x = max(n, m). Twój algorytm jest złożoności O(2^(Poly(log(x)))), a więc wykładniczo gorszej. Mój algorytm jest też krótszy w implementacji.

kgkg napisał(a):

Miałem napisać funkcję sprawdzającą, czy dwie liczby mają te same dzielniki pierwsze. Czy funkcja poniżej jest ok, czy możaby coś poprawić, żeby szybciej działała?

int a(int m, int n)
{
int i;
	for (i=2; i<=m; i++)
	{
		if(m%i==0)
		{
			if(n%i!=0) return 0;
			else
			{
				while (m%i==0) m=m/i;
				while (n%i==0) n=n/i;
			}
		}}
			if(n>=2) return 0;
			else return 1;
}

Litości z tym formatowaniem:

int a(int m, int n)
{
    int i;
    for (i = 2; i <= m; i++) {
        if (m % i == 0) {
            if (n % i != 0)
                return 0;
            else {
                while (m % i == 0)
                    m = m / i;
                while (n % i == 0)
                    n = n / i;
            }
        }
    }
    if (n >= 2)
        return 0;
    else
        return 1;
}

Nie wiem czemu uważasz, że to jest dobrze. Już tak linijka jest ewidentnie źle:

            if (n % i != 0)
                return 0;

rozwiązanie prymitywne:

unsigned mulUniqueFactorizationOf(unsigned x)
{
    unsigned result = 1;
    if (x % 2 == 0)
    {
        result = 2;
        while (x % 2 == 0) x /= 2;
    }
    for (unsigned y = 3; x != 1; y += 2) {
        if (x % y == 0) {
            result *= y;
            while (x % y == 0) x /= y;
        }
    }
    return result;
}

bool haveSamePrimeFactors(unsigned a, unsigned b)
{
    return mulUniqueFactorizationOf(a) == mulUniqueFactorizationOf(b);
}

Szybkie rozwiązanie:

#include <numeric>
bool prime_divisors_is_subset(uint64_t n, uint64_t m)
{
    uint64_t g = 2;
    while (g > 1) {
        g = std::gcd(n, m);
        m = g;
        n /= g;
    }
    return n == 1;
}

bool prime_divisors_equal_sets(uint64_t n, uint64_t m)
{
    return prime_divisors_is_subset(n, m) && prime_divisors_is_subset(m, n);
}