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

0

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

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.

0

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.

0

' 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 '

1

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

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

0

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.

1
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);
}
0

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0