Dzielniki i czynniki pierwsze liczb

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;
 
}
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
1
Shalom napisał(a):
  1. Postępujemy tak dopóki liczba > 1

... oraz dzielnik mniejszy niż liczba

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?

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.

0

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

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)).

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.

0

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

0

Poczytaj, napisz, wklej, poprawimy.

0

Ok

0

@_13th_Dragon: zgłosił kosmetyczne poprawki, które zmniejszą ilośc kodu i poprawią czytelność, chociaż z samym algorytmem sita bym nie kombinował, natomiast istota i złożoność są bez zmian.

0

Nie prawda, masz złożoność O(N) zaś da się zrobić O(sqrt(N))

0

Chodzi Ci o factors, to prawda, to jest poprawiony jego kod, niewielkie usprawnienie daje O(sqrt(n)).

0

Przy tym kodzie wyskakuje błąd kompilacji

0
Jan Ciupa napisał(a):

Przy tym kodzie wyskakuje błąd kompilacji

Więc masz za stary kompilator.

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