Rozkład liczb na czynniki :: 4programmers.net

2017-12-13T18:30:10+01:00

Rejestracja: dni
Ostatnio: dni

Dany jest ciąg n liczb, który podawany jest z poziomu klawiatury. Program musi rozpoznać ile w podanym ciągu znajduje się liczb, które spełniają warunek, że w ich rozkładzie na czynniki pierwsze znajdują się kolejne liczby pierwsze.
np.
Warunek spełnia: 12 -> 12=223
Warunku nie spełnia: 55 -> 5*11

Jest to zadanie, na którego wykonaniu bardzo mi zależy, jak dotąd najtrudniejsze, jakiemu muszę sprostać. Poza wprowadzeniem danych nie mam pojęcia, co zrobić. Bardzo proszę o pomoc, będę wdzięczny, tym bardziej, że w przyszłości nie będę miał problemu z takiego typu zadaniami.
Pozdrawiam

MarekR22

2017-12-13T19:04:10+01:00

Rejestracja: dni
Ostatnio: dni

Troszkę armata dla ciebie, ale powinno pomóc.

spartanPAGE

2017-12-13T19:39:25+01:00

Rejestracja: dni
Ostatnio: dni

To twój szczęśliwy dzień.

Kopiuj

#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
#include <cassert>

auto sieve(int limit) {
	std::vector<bool> primes_lookup(limit);
	// kod z neta
	unsigned long long int i,j;
	
    for (i=2;i<limit;i++)
    	primes_lookup[i]=1;
    	
    for (i=2;i<limit;i++)
    	if (primes_lookup[i])
            for (j=i;i*j<limit;j++)
                primes_lookup[i*j]=0;
        
	return primes_lookup;
}

template<typename Cont>
auto extract_primes(Cont const &primes_lookup) {
	std::vector<int> result;
	for (int i = 0; i < primes_lookup.size(); ++i) {
		if (primes_lookup[i]) {
			result.push_back(i);
		}
	}
	return result;
}

template<typename Cont>
auto calc_factors(Cont const &primes, int num) {
	std::vector<int> result;
	
	for (int i = 0; i < primes.size() && primes[i] <= num;) {
		if (num % primes[i]) {
			i += 1;
			continue;
		} else {
			result.push_back(primes[i]);
			num /= primes[i];
		}
	}
	return result;
}

int main() {
	auto const primes = extract_primes(
		sieve(100000)
	);

	auto calc_factors = [&primes](int num) {
		return ::calc_factors(primes, num);
	};
	
	// a spróbuj tylko pchać jakieś factorsy które nie są posortowane i które nie są l. pierwszymi
	auto condition = [&primes](auto factors) -> bool {
		if (!factors.size()) return false;
		
		auto last = std::unique(std::begin(factors), std::end(factors));
		return std::equal(
			std::begin(factors),
			last,
			std::find(std::begin(primes), std::end(primes), factors[0])
		);
	};
	
	for(int num = 0; std::cin >> num;) {
		auto factors = calc_factors(num);
		std::cout
			<< (condition(factors)? "warunek spelnia " : "warunku nie spelnia ")
			<< num
			<< " -> ";

		for(auto el: factors) std::cout << el << " ";

		std::cout << std::endl;
	}
	return 0;
}

https://ideone.com/St5yH2

stdin:

Kopiuj

12 55 130 1 2 10 300 13

stdout:

Kopiuj

warunek spelnia 12 -> 2 2 3 
warunku nie spelnia 55 -> 5 11 
warunku nie spelnia 130 -> 2 5 13 
warunku nie spelnia 1 -> 
warunek spelnia 2 -> 2 
warunku nie spelnia 10 -> 2 5 
warunek spelnia 300 -> 2 2 3 5 5 
warunek spelnia 13 -> 13

Aisekai

2017-12-13T19:45:43+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 375

Mógłbyś sitem erastotensa wyznaczyć wszystkie liczby pierwsze od 1-liczba i dodać je do vectora.
Stworzyc jakaś zmienną (może być boolowska) i ustawić ją na true. Sprawdzasz czy otrzymane liczby pierwsze dziela twoją bez reszty. Jeżeli w jakimś momencie by się okazało że nie dzieli - zmieniasz wartość zmiennej na false i sprawdzasz dla kolejnych. Jeżeli teraz by jakaś dzieliła, to liczba nie spełnia. Jeżeli dalej by już żadna nie dzieliła - liczba spełnia ten warunek.
Edit: źle zrozumiałem pytanie. Ale można to naprawić, ustawiając tą flagę na true, dla pierwszej napotkanej liczby pierwszej będącej dzielnikiem twojej liczby.