Dzielniki i czynniki pierwsze liczb

Odpowiedz Nowy wątek
2019-10-04 23:12
0

Cześć!
Mam problem z zadaniem, próbowałem je rozwiązać samodzielnie ale niestety nie potrafię.
Tutaj jest polecenie zadania:
Dzielniki i czynniki pierwsze liczby
Napisz program który wyznaczy rozkład liczby na czynniki pierwsze oraz wypisze wszystkie
dzielniki liczby i ilość dzielników.
Wejście:
Liczba x (0<=x<=1000000)
Wyjście:
W kolejnych liniach program powinien wypisać:
• Linia 1: czynniki pierwsze (oddzielone spacją) lub słowo „BRAK” jeżeli liczby nie da się
rozłożyć na czynniki pierwsze
• Linia 2: dzielniki (oddzielone spacją) lub słowo „BRAK” jeżeli liczba nie ma żadnych
dzielników
• Linia 3: ilość dzielników

Generalnie program działa, ale nie wiem jak napisać jaka jest ilość dzielników i przy nie których liczbach są złe wyniki. Jak daje program do sprawdzenia to mam 0 punktów także coś jest nie tak.
Miałbym prośbę aby napisać co tu nie gra :D i podesłać rozwiązanie.

Tutaj są moje wypociny:

#include <iostream>
#include <cmath>
#include <cstdlib>

using namespace std;

bool czy_pierwsza(int n)
{
    if(n<2)
        return false;

    for(int i=2;i*i<=n;i++)
        if(n%i==0)
            return false; 
    return true;
}

void czynniki(unsigned n)
{

if(czy_pierwsza(n))
        cout<<"BRAK"<<endl;
        else if(n == 1)
        {
           cout<<"BRAK"<<endl;
           cout<<"1";
        }

    else
    {
unsigned g,i;

    g = sqrt(n);

    for(i = 2; i <= g; i++)
    {
        while(n % i == 0)
        {
            cout << i << " ";
            n /= i;
        }
    }
    cout<<endl;
}
}

int main()
{
int b;

    unsigned long long n;
    cin>> n;
    czynniki(n);
    long long gg=sqrt(n);
    if(n>1)
    {
    for(int i=1; i<=gg; i++) 
    {
        if(n % i == 0)
            cout << i << " ";
    }
    for(int i=int(gg); i>=2; i--) 
    {
        if(n % i == 0)
            cout <<n / i<<" ";
        }
    cout<<n<<endl;
    cout.flush();
}

if(czy_pierwsza(n))
{
  cout<<"2";
}
    return 0;

}
edytowany 2x, ostatnio: Jan Ciupa, 2019-10-05 00:25
Co się dzieje, nie kompiluje się, wyjątek, złe wyniki? - lion137 2019-10-05 00:19

Pozostało 580 znaków

2019-10-05 01:09
1

Skoro masz zliczać dzielniki to cały ten algorytm (zapewne kradziony :D) do kosza. Wystarczy pomyśleć 2 minuty a nie bezmyślnie kopiować z internetu:

  1. Szukamy dzielnika liczby idąc od dołu
  2. Jeśli trafimy na dzielnik to dzielimy liczbę przez ten dzielnik i zapisujemy sobie gdzieś na boku (w jakiejs mapie np.) że taki dzielnik wystąpił i uwaga: w tej sytuacji nie przeskakujemy dalej, tylko kolejny raz testujemy tą samą liczbę, bo przecież 8 = 2*2*2, więc dzielnik X może wystąpić wiele razy
  3. Postępujemy tak dopóki liczba > 1

Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2019-10-05 01:10

Pozostało 580 znaków

2019-10-05 01:26
1
Shalom napisał(a):
  1. Postępujemy tak dopóki liczba > 1

... oraz dzielnik mniejszy niż liczba


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
z tym że wystarczy ... oraz dzielnik mniejszy niż kwadrat liczby - _13th_Dragon 2019-10-05 02:26
tylko jeśli razem z dzielnikiem zapisze sobie wynik z dzielenia, oraz dzielnik mniejszy lub równy kwadratowi - sig 2019-10-05 06:36
@sig jak nie zapisze to utknie na punkcie 2, natomiast co do mniejszy lub równy - racja - _13th_Dragon 2019-10-05 08:34

Pozostało 580 znaków

2019-10-05 10:19
0

Ale jak to zapisać w kodzie? Bo trochę nie rozumiem. Z tego co napisałeś to będzie pętla o ile się nie mylę tylko jak to zrobić aby sprawdziło jeszcze raz np 2?

edytowany 1x, ostatnio: Jan Ciupa, 2019-10-05 10:19

Pozostało 580 znaków

2019-10-05 12:58
0

Dodatkowy while wewnątrz fora
lub
Zwiększasz licznik tylko jeżeli nie dzieli się na całość.

A tak w ogóle zainteresuj się sitem Eratostenesa.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 2x, ostatnio: _13th_Dragon, 2019-10-05 12:59

Pozostało 580 znaków

2019-10-05 13:34
0

Ok, poczytam o tym i spróbuję to zrobić.

Pozostało 580 znaków

2019-10-05 13:40
0

Tu Masz to z sitem i podzielone na funkcje, jak sito to za skomplikowane, to Możesz faktoryzować tak jak teraz i drukować sobie dzielniki; factors zwraca wektor dzielników, a jako ostatni element ich ilość (do milona powinno wystarczyć sito do 1000).

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <ctime>
using namespace std;

void printArray(std::vector<int>); // debug help

std::vector<int> sieve(int n);
std::vector<int> factorize(int n);

std::vector<int> factors(int n);
// Globals:
std::vector<int> PRIMES = sieve(10000);
std::unordered_set<int> prime_set (PRIMES.begin(), PRIMES.end());

int main() {

    printArray(factorize(99));
    // -> [3 3 11]
    printArray(factors(1000));
    // -> [1 2 2 2 5 5 5 1000 8]

    return 0;
}

std::vector<int> sieve(int n) {
    n = n + 1;
    std::vector<bool> arr(n);
    std::vector<int> out;
    int j{0};
    int k{0};
    for (int i = 0; i < n; ++i)
        arr[i] = true;
    for (int i = 2; i * i <= n; ++i){
        if (arr[i]) {
            j = i * i;
            k = 1;
            while (j < n) {
                arr[j] = false;
                j = i * i + k * i;
                k += 1;
            }
        }
    }
    for (size_t i = 2; i < arr.size(); ++i) {
        if (arr[i])
            out.push_back(i);
    }
    return out;
}

std::vector<int> factorize(int n) {
    std::vector<int> out;
    for (auto & e : PRIMES) {
        while (n % e == 0) {
            out.push_back(e);
            n /= e;
        }
    }
    return out;
}

std::vector<int> factors(int n){
    std::vector<int> out;
    int i = 1;
    while (i * i <= n){
            if (n % i == 0){
                out.push_back(i);
                if (n / i != i) {
                    out.push_back(n / i);
                }
            }
            i++;
    }

        out.push_back(out.size());
        return out;
}

void printArray(std::vector<int> a) {
    cout <<"[";
    for (auto & e : a) 
        cout << e << " ";
    cout <<"]";
    cout << endl; 
}

EDIT: Poprawiłem funkcję factors, był bug:) i przerobiona na O(sqrt(n)).


edytowany 2x, ostatnio: lion137, 2019-10-05 17:53

Pozostało 580 znaków

2019-10-05 14:06
0
lion137 napisał(a):
std::vector<int> sieve(int n);
std::vector<int> factorize(int n);
std::vector<int> factors(int n);
std::vector<int> PRIMES = sieve(10000);

Używasz std::vector<int> bardzo dużo razy czemu nie zrobić typedef'a

lion137 napisał(a):
std::vector<int> PRIMES = sieve(10000);
std::unordered_set<int> prime_set (PRIMES.begin(), PRIMES.end());

Po kiego ci dwa kontenery zawierające to samo?

lion137 napisał(a):
  for (int i = 0; i < n; ++i)
      arr[i] = true;

Doprawdy? Czemu nie użyć:

std::vector<bool> arr(n,true);

?

lion137 napisał(a):
          while (j < n) {

Używająć for wychodzi znacznie krótszy a za tym czytelniejszy zapis.


            for(int ii=i<<1,k=ii;k<n;k+=ii) arr[k]=false;

i tyle!

Doszedłem do połowy i mi się znudziło.
W sumie to się nie nadaje do użytku.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2019-10-05 14:06

Pozostało 580 znaków

2019-10-05 14:13
0

Czyli jak w końcu ma wyglądać ten kod? 😵

Pozostało 580 znaków

2019-10-05 14:15
0

Poczytaj, napisz, wklej, poprawimy.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2019-10-05 14:17
0

Ok

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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