bool isPrime(int number)
{
number = abs(number);
if(number == 0||number == 1){
return false;
}
int divisor;
for(divisor = number / 2;number % divisor != 0;--divisor);
return divisor == 1;
}
Найти самую длинную последовательность простых чисел в массиве(С++).
Задан линейный массив. Найти в нем самую длинную цепочку чисел которые являются простыми числами
Вы уже умеете программно отличать простые числа от не простых?
Цитата: Nikes
Задан линейный массив. Найти в нем самую длинную цепочку чисел которые являются простыми числами
Похожие темы,внизу страницы не смотришь ? Зря. Нахождение простых чисел там есть,поиск последовательности тоже.У тебя задача, собственно, состоит из 2 частей: нужна функция проверки числа на простоту и поиск самой длинной последовательности таких чисел в массиве.Используй STL для поиска последовательности, соответствующей определенному условию,а именно алгоритм search_n.Или STL использовать,как обычно, нельзя ?
Можете дать сылки на эти теми? а то немогу найти :confused:
Цитата: Nikes
Можете дать сылки на эти теми? а то немогу найти :confused:
http://forum.codenet.ru/search.php?searchid=103199 Тут про поиск простых чисел в разделе Студентам.В частности смотри эту тему - поиск простых чисел в С++.
Посмотревшы по поиску, серовно ниче кроме нахождения простых чисел лучшего ненашел. Задача то у меня не токо поиск чисел но и найти максемальную цепочку в масиве,в етом и самая большая трудность для меня в этой задаче.(STL можна использовать)
А где проблема то?
Берешь в цикле и смотришь, если простое то плюс единичка к количеству, как только не простое, сравниваешь его с максимальным если больше то максимальное равно кол-ву, таким образом найдешь максимальное, потом второй раз пролистываешь массив и считаешь, при этом запоминая на каком индексе массива началась последовательность, если кол-во равно максимальному то выводишь на экран массив с индекса начала последовательности по конец.
Берешь в цикле и смотришь, если простое то плюс единичка к количеству, как только не простое, сравниваешь его с максимальным если больше то максимальное равно кол-ву, таким образом найдешь максимальное, потом второй раз пролистываешь массив и считаешь, при этом запоминая на каком индексе массива началась последовательность, если кол-во равно максимальному то выводишь на экран массив с индекса начала последовательности по конец.
Напиши функцию проверяющую является ли число простым.Написал ? Например что-нибудь такое
Теперь можешь попробовать выводить только простые числа.Это функция работает достаточно медленно,в теме,что я приводил раннее ссылку,смотри код cheburator.Можешь взять там.Далее как я уже говорил, используешь алгоритм search_n - это поиск первых n последовательных совпадений.Тебе нужна форма этой функции с бинарным предикатом,которая возвращает позицию первого из соunt последовательных элементов в интервале begin() - end(),для которых бинарный предикат возвращает true.Бинарный предикат.Вот он
Тогда вызываешь так
Теперь сама реализация: создаешь вектор,допустим из 30 элементов и
заполняешь его случайными числами в диапазоне от 2 до 7 - в этом диапазоне 4 простых числа: 2,3,5,7).Поскольку тебе нужна самая длинная последовательность простых чисел считай что первоначально она равна coll.size() - длине самого массива.Идешь в цикле от coll.size() и ищешь первое совпадение - это и будет самая длинная последовательность простых чисел.Как только нашел - break; Все. Пробуй.
Код:
Теперь можешь попробовать выводить только простые числа.Это функция работает достаточно медленно,в теме,что я приводил раннее ссылку,смотри код cheburator.Можешь взять там.Далее как я уже говорил, используешь алгоритм search_n - это поиск первых n последовательных совпадений.Тебе нужна форма этой функции с бинарным предикатом,которая возвращает позицию первого из соunt последовательных элементов в интервале begin() - end(),для которых бинарный предикат возвращает true.Бинарный предикат.Вот он
Код:
bool binaryIsPrime(int elem,int){
return isPrime(elem);
}
return isPrime(elem);
}
Код:
vector<int>::iterator pos = searcn_n(coll.begin(),coll.end(),
count,//счетчик
0, // фиктивное значение
binaryIsPrime); Критерий
count,//счетчик
0, // фиктивное значение
binaryIsPrime); Критерий
Теперь сама реализация: создаешь вектор,допустим из 30 элементов и
заполняешь его случайными числами в диапазоне от 2 до 7 - в этом диапазоне 4 простых числа: 2,3,5,7).Поскольку тебе нужна самая длинная последовательность простых чисел считай что первоначально она равна coll.size() - длине самого массива.Идешь в цикле от coll.size() и ищешь первое совпадение - это и будет самая длинная последовательность простых чисел.Как только нашел - break; Все. Пробуй.