Генерация последовательности с использованием только простых чисел 2, 3 и 5, а затем отображение n-го члена (C ++)
Я работаю над проблемой, которая просит сгенерировать последовательность, используя простые числа 2, 3 и 5, а затем отображая затем n-е число в последовательности. Итак, если я прошу программу отобразить 1000-е число, оно должно отобразить его.
Я не могу использовать массивы или что-то подобное, просто базовые решения и циклы.
Я начал работать над этим и ударил стену … вот что я получил:
#include <iostream>
using namespace std;
int main() {
unsigned int n=23;
for(int i=2; i<n; i++){
if(i%2==0){
cout<<i<<", ";
}else if(i%3==0){
cout<<i<<", ";
}else if(i%5==0){
cout<<i<<", ";
}
}
return 0;
}
К сожалению, этот код не делает то, что требуется. Он отображает числа, такие как 14, который включает в себя простое число 7 …. Числа могут быть разделены только на 3 указанных простых числа (2,3,5).
Я нашел некоторую информацию, которую я пытаюсь понять, и до сих пор не уверен, как это реализовать … может быть, с использованием большого количества циклов for ()? Итак, похоже, я должен использовать концепцию 2 ^ n * 3 ^ m * 5 ^ k, где n + m + k> 0.
Я предполагаю, что мне нужно провести число через тест, где сначала проверяется, полностью ли оно делится на 2 ^ 1 * 3 ^ 0 * 5 ^ 0, затем 2 ^ 0 * 3 ^ 1 * 5 ^ 0, затем 2 ^ 0 * 3 ^ 0 * 5 ^ 1 и так далее … Просто не знаю, с чего начать.
Решение
Проверь это.
#include <iostream>
using namespace std;
int IsPrime(int var);
int CheckifPrimeGreaterThaFive(int Num);
int GetFactors(int Num)
{
int i =0,j=0;
for (i =2,j=0; i <= Num; i++)
{
if (Num%i == 0)
{
if (1 == CheckifPrimeGreaterThaFive(i))
{
return 1;
}
}
}
return 0;
}
int CheckifPrimeGreaterThaFive(int Num)
{
if ((Num != 2 && Num != 3 && Num != 5) && IsPrime(Num))
{
return 1;
}
return 0;
}
int IsPrime(int var)
{
for (int i = 2; i <= var/2; i++)
{
if (var % i == 0)
return 0;
}
return 1;
}int main() {
int n=98;
int i, FactorsCount=0;
for(i=2; i<n; i++)
{
if (0 == GetFactors(i))
{
cout<<" "<<i;
}
}
return 0;
}
Другие решения
Это известная проблема, названная проблемой Хэмминга после Ричарда Хэмминга, и она освещена в известной книге Дисциплина программирования Дейкстра. Математики называют эти числа (если вы включаете 1) 5-гладкими числами, поскольку их простые разложения содержат только простые числа, меньшие или равные 5.
Вы должны заметить, что вы можете генерировать числа друг от друга. Вот один из способов думать о проблеме:
#include <set>
#include <iostream>
using namespace std;
int
main()
{
const unsigned n = 23;
set<unsigned> s;
s.insert(2);
s.insert(3);
s.insert(5);
for (unsigned i = 0; i < n; ++i)
{
// This returns the smallest element in the set.
unsigned x = *s.begin();
cout << x << '\n';
// Erase the smallest element.
s.erase(s.begin());
// Insert the multiples of x.
s.insert(2*x);
s.insert(3*x);
s.insert(5*x);
}
}
Это займет O (n log n) время, чтобы напечатать n чисел. Это можно сделать за O (n) раз, используя аналогичный алгоритм, объединяя ленивые потоки. Мое решение использовано boost::transform_iterator а также boost::iterator_facade, поэтому я бы не рекомендовал это новичку.
Этот код сделает это. Разбиение проблемы на более мелкие проблемы часто является хорошим планом.
int main() {
unsigned int n=23;
unsigned int counter=0;
unsigned int answer;
for ( answer = 2; counter < n; ++answer ) {
if ( isNotDivisibleByAPrimeGreaterThan5( i ) {
++counter;
}
}
cout << answer;
return 0;
}
Теперь вам нужно только написать эту функцию.
bool isNotDivisibleByAPrimeGreaterThan5( unsigned int i ) {
// return true if i is not divisable by a prime greater than 5.
}
#include <type_traits>
#include <utility>
#include <iostream>
template<int... s>
struct seq {};
template<int n, typename seq, typename=void>
struct can_be_factored_into;
template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && (n%first) >::type >: can_be_factored_into< n, seq<rest...> > {};
template<int n, int first, int... rest>
struct can_be_factored_into< n, seq<first, rest...>, typename std::enable_if< (n > 1) && !(n%first) >::type >: can_be_factored_into< n/first, seq<first, rest...> > {};
template<int n, int... rest>
struct can_be_factored_into< n, seq<rest...>, typename std::enable_if< n == 1 >::type: std::true_type {};
template<int n>
struct can_be_factored_into< n, seq<>, typename std::enable_if< n != 1 >::type: std::false_type {};
template<int n>
using my_test = can_be_factored_into< n, seq<2,3,5> >;
template<template<int n>class test, int cnt, int start=1, typename=void>
struct nth_element;
template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt>1)&&test<start>::value >::type >:
nth_element<test, cnt-1, start+1 > {};
template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< (cnt==1)&&test<start>::value >::type >
{ enum { value = start }; };
template<template<int n>class test, int cnt, int start>
struct nth_element<test, cnt, start, typename std::enable_if< !test<start>::value >::type >:
nth_element<test, cnt, start+1 > {};
int main() {
std::cout << nth_element< my_test, 1500 >::value << "\n";
}
Как только вы скомпилируете приведенный выше код, он будет выполнен менее чем за 1 минуту.
Недостатком является то, что он будет превышать предел рекурсии времени компиляции большинства компиляторов. (это было ваше ежедневное занижение)
Чтобы улучшить это, nth_element должен быть переписан, чтобы сделать экспоненциальный поиск взрыва и разделяй и властвуй в этом диапазоне. Возможно, вам также придется изменить код для работы с 64-битными значениями, поскольку 1500-й элемент упомянутой последовательности может быть больше, чем 2 ^ 32.
Или быстро компилировать это тоже требование? 🙂
И вот первый проход в реализации Хэмминга. Еще не скомпилировано:
#include <iostream>
#include <utility>
template<long long... s>
struct seq;
template<long long cnt, typename seq, typename=void>
struct Hamming;
template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt == 0 >::type> {
static const long long value = first;
};
template<long long x, typename seq>
struct prepend;
template<long long x, long long... s>
struct prepend<x, seq<s...>>
{
typedef seq<x, s...> type;
};
template<typename s1, typename s2, typename=void>
struct merge;
template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 < begin_s2) >::type > {
typedef typename prepend< begin_s1, typename merge< seq< s1... >, seq< begin_s2, s2... > >::type >::type type;
};
template<long long begin_s1, long long... s1, long long begin_s2, long long... s2>
struct merge< seq< begin_s1, s1... >, seq< begin_s2, s2... >, typename std::enable_if< (begin_s1 >= begin_s2) >::type > {
typedef typename prepend< begin_s2, typename merge< seq< begin_s1, s1... >, seq< s2... > >::type >::type type;
};
template<long long begin_s1, long long... s1>
struct merge< seq< begin_s1, s1... >, seq<>, void > {
typedef seq< begin_s1, s1... > type;
};
template<long long... s2>
struct merge< seq<>, seq<s2...>, void > {
typedef seq< s2... > type;
};
template<long long cnt, long long first, long long... rest>
struct Hamming<cnt, seq<first, rest...>, typename std::enable_if< cnt != 0 >::type>:
Hamming<cnt-1, typename merge< seq<first*2, first*3, first*5>, seq<rest...> >::type >
{};
int main() {
std::cout << Hamming<1500, seq<1>>::value << "\n";
};