ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1586. Трипростые числа

Need help
Послано Georgiy Savchenko 6 ноя 2007 14:49
Hey all, could onyone point my error out?

I have solved the problem for n = 4 and got right result, but I cannot go ahead to n = 5.
At each step from 4 to n inclusive I am keeping how many treeprime numbers exist for all possible two last digits - function Count (for instance, treeprimenumbers end with AB: Count(AB) = X; end with CD: Count(CD) = Y).
To go aheah to n = n + 1 I am trying to add digit L from the set {1, 3, 7, 9} (all possible end digits for prime numbers) at the end of each possible last digits cases, getting ABL, CDL, and so on. Then I check if the result number ABL, CDL, ... is a prime one. If yes, then I define a new function CountNew, writing CountNew(BL) = CountNew(BL) + Count(AB) (explanation: increase number of treeprime numbers that end with BL, increasing is the number of treeprime numbers end with AB).
Having completed the step, I perform Count = NewCount.

This approach gives right result for n=3 and 4, but not 5 (I found it out by a bruteforce solution)

Am I missing something?

Edited by author 06.11.2007 14:49

Edited by author 06.11.2007 14:50
Re: Need help
Послано Georgiy Savchenko 12 ноя 2007 20:16
Finally got it. Had a pretty stupid error, the described approach is correct :)