Стажировка

Тестовое задание программиста С

Найти самую длинную возрастающую цепочку простых чисел

В заданном бинарном файле необходимо найти самую длинную возрастающую

цепочку простых чисел. Бинарный файл трактуется как последовательность 6-ти

байтовых беззнаковых целых. Размер файла может быть любым, если размер файла не кратен 6, то лишние байты с конца файла игнорируются. Элементы цепочки не обязаны идти друг за другом в файле, между элементами цепочки могут встречаться не простые числа в любом количестве. Из двух цепочек одинаковой длины предпочтение отдается той, у которой первый элемент больше. Если длины и первые элементы цепочек совпадают, предпочтение отдается той, у которой смещение первого элемента меньше.

Задача должна быть реализована в виде консольного приложения для Linux

32bit (дистрибутив - на Ваше усмотрение) и должна быть выполнена на языке C. Файл с данными указывается как параметр командной строке. Во время выполнения должен отображаться прогресс обработки файла. 

Результатом работы должен быть вывод первого элемента цепочки и его смещения,

последнего элемента цепочки и его смещения и длины цепочки, или, если цепочка не

была найдена – сообщение об этом прискорбном факте.

Примеры формата файла:

Содержание файла (byte, hex, 34 байта): 

01 00 00 00 00 00 02 00 

00 00 00 00 03 00 00 00

00 00 00 00 00 00 00 80

00 00 00 00 80 00 FF FF

FF FF

Числа в файле: 1, 2, 3, 140737488355328, 549755813888

Примеры последовательностей и найденные цепочки:

Последовательность    Найденная цепочка

2, 3, 5, 3, 5, 7, 11        3, 5, 7, 11

2, 3, 4, 5, 6, 7, 3, 5, 7     2, 3, 5, 7

2, 3, 10,5, 6, 7, 3, 5, 7    2, 3, 5, 7

2, 3, 3, 5, 6, 7, 3, 5, 7     3, 5, 7

2, 3, 5, 3, 5, 11          3, 5, 11

2, 3, 5, 2, 5, 11          2, 3, 5

При передаче решения необходимо предоставить исходные коды, скрипт для сборки, при необходимости, короткую инструкцию по сборке. Преимуществом является скрипт для тестирования разработанной программы на указанных выше цепочках.

Все вопросы по условию задачи решаются на Ваше усмотрение, однако, если у

Вас возник вопрос – напишите о нем и о выбранном решении в сопроводительном

письме.

Необходимо учитывать, что решение будет тестироваться на файлах большого размера (>10Мб), поэтому просьба уделить особое внимание эффективности решения.

Так же просьба подготовить некоторые тестовые последовательности (директорию с файлами), которые, по Вашему мнению, покрывают различные вариант расположения простых числе в последовательности.