Rozkład silnii :: 4programmers.net

Votu

2019-02-01T09:28:17+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 6

0

Witam, mam problem z rozkładem silni na czynniki pierwsze. Na początek tworzę tablicę i zliczam licznik liczb pierwszych, następnie tworzę tablicę o tym rozmiarze i zapisuje w niej te liczby. Później tworzę kolejną tablicę o tym samym rozmiarze i przypisuje jej wartość zero dla każdego elementu. Chciałem zrobić tak, żeby np. dla 5!=543*2, każdy z tych elementów rozłożyć na czynniki pierwsze, i jeśli się rozkłada to Tablicę C zwiększyć o 1, i tak rozłożyć wszystkie liczby. No tylko gdzieś mój pomysł nie jest dobry, i tu przychodzę z pytaniem gdzie?

Kopiuj

#include <iostream>
using namespace std;

int main()
{
    unsigned n;
    cout<< "Podaj liczbe naturalna n: ";
    cin>>n;
    int licznik=0;

    bool *TAB=new bool[n+1];
    for(int i=2; i<n+1; i++)
        TAB[i]=0;

    for (int i=2; i*i<=n; i++)
    {
        if(!TAB[i])
            for (int j = i*i ; j<n+1; j+=i)
                TAB[j] = 1;
    }

    for (int i=2; i<n+1; i++)
        if(!TAB[i])
            licznik++;

    int *B=new int [licznik-1];
    
    int j=0;
    for (int i=2; i<n+1; i++)
        while(!TAB[i])
        {
            B[j]=i;
            j++;
            break;
        }

    delete [] TAB;
    
    int *C=new int [licznik-1];
    for(int i=0; i<=licznik-1; i++)
        C[i]=0;


    for(int i=n; i>1; i++)
         {
           while(n%B[j]==0 && j<=licznik-1)
            {
                C[j]++;
                n/=B[j];
            }
            j++;
        }
  
 return 0;

}

kaczus

2019-02-01T10:01:16+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Łódź
Postów: 1403

0

usuwasz tablicę B delete [] TAB; a potem próbujesz wykorzystywać.... n/=B[j]; tu jest problem. Drugi jest taki, że 2 razy powołujesz tablicę B do życia, przez co tracisz wskaźnik i masz pamięć niezwolnioną.

Votu

2019-02-01T10:09:46+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 6

0

A to nie tak, że jak stworzyłem tablicę B i ją już uzupełniłem korzystając z tej pierwszej tablicy ( TAB) to mogę tą tablicę (TAB) usunąć?

Bo później już nie korzystam z tablicy (TAB) a tablicy B.

W przedostatniej pętli zamiast i++ powinno być i-- ;)
Ale nadal szukam co nie tak.

lion137

2019-02-01T12:03:24+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 5027

0

Co ma być na wejściu, co na wyjściu? Bo nie rozumiem; Chcesz rozłożyć liczbę n! na czynniki pierwsze? Tzn. dla n = 5, czyli n! = 120, program ma zwrócić [2, 2, 2, 3, 5], co jest równoznaczne z rozłożeniem wszystkich czynników silni. Czy coś innego?

Votu

2019-02-01T12:12:15+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 6

0

Napisac program, który dla podanej przez uzytkownika liczby naturalnej
1 < n < 10000 wyznaczy rozkład liczby n! (n silnia) na czynniki pierwsze. Na przykład
dla n = 10 program powinien wyswietlic odpowiedz 10! = 2^8 x3^4 x 5^2 x 7^1

MarekR22

2019-02-01T12:18:12+01:00

Rejestracja: dni
Ostatnio: dni

0

Rozkład silni na czynniki pierwsze.
Skoro silnia rośnie szybko i jest iloczynem kolejnych liczb, to można użyć podstępu.
Prościej jest wpisać do kodu rozkład na czynniki pierwsze dla kilku kolnych liczb całkowitych i potem zamiast liczyć silnię i potem ją rozkładać, połączyć rozkłady na czynniki pierwsze dla kolejnych liczb.
Jeśli potrzebujesz rozkład dla dużych n to ta metoda też jest dobra, bo generowanie tych rozkładów można sprytnie uprościć modyfikując algorytm sita Eratostenesa (zamiast oznaczania, że coś nie jest liczbą pierwszą, to uzupełnia się rozkłady na czynniki pierwsze.

Votu

2019-02-01T12:26:04+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 6

0

Kopiuj

  int x=n;

  for(int i=x; i>1; i--)
      {
          for(int j=0; j<=licznik-1; j++)
            while(n%B[j]==0)
            {
                C[j]++;
                n/=B[j];

            }
      }

Zmieniłem ostatnią pętle na taką, teraz myślę, że trzeba ustawić ponownie n=x;, bo tak n=1, więc while zadziałał by tylko dla jednej liczby.
Pomysł taki, żeby napisać końcową pętlę w której napiszę że B[i]^C[i]*... itd

lion137

2019-02-01T14:41:37+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 5027

1

Mam, jak widać nie jest za szybki, naiwnie, tworzy sito, i iterując do n, jak nie jest pierwsza to faktoryzuje (mowa o factorizeFactorial) i dorzuca do wyniku, po czym jeszcze posortowanie dla czytelności. Zastanawiam się nad przyśpieszeniem, coś jak sugeruje @MarekR22 , chociaż na oko, złożoność wydaje się taka sama.
std::unordered_set po to, aby mieć lookup w czasie stałym: http://www.cplusplus.com/reference/unordered_set/unordered_set/

Kopiuj

#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> factorizeFactorial(int n);
// Globals:
std::vector<int> PRIMES = sieve(10000);
std::unordered_set<int> prime_set (PRIMES.begin(), PRIMES.end());

int main() {

	printArray(factorizeFactorial(10));
	// -> [2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 5, 5, 7]
	printArray(factorizeFactorial(5));
	// -> [2, 2, 2, 3, 5]
	clock_t begin = clock();
	for (int i = 0; i < 100; ++i)
		factorizeFactorial(999);
	clock_t end = clock();
	double secs = double(end - begin) / CLOCKS_PER_SEC;
	cout << secs << endl; // -> 3.09726
	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> factorizeFactorial(int n) {
	std::vector<int> primes;
	for (auto & p : PRIMES) {
		if (p <= n)
			primes.push_back(p);
	}
	std::vector<int> tmp;
	std::vector<int> out = primes;
	
	for (int i = 2; i <= n ; ++i) {
		std::unordered_set<int>::const_iterator found = prime_set.find(i);
		if (found == prime_set.end()) { // if i is not prime
			tmp = factorize(i);
			for (auto & e : tmp)
				out.push_back(e);
		}
	}
	std::sort(out.begin(), out.end());
	return out;
}

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