Задача Е. Прости числа

Простите числа и техните свойства са били изучавани още в древността от гръцките математици. Евклид е един от тези учени, дали своя голям принос. Той доказва, че има безкрайно много прости числа и всяко естествено число може да се запише по единствен начин като произведение съставено от прости числа. Да разкажем целия труд на Евклид или да споменем имената на всички, допринесли за изучаването на тези числа до наши дни, би ни отнело твърде много време. Въпреки че са познати още от древността, и днес простите числа вълнуват математиците. Също така, простите числа намират и широко приложение в живота – например те се използват в много криптографски системи. Историята и приложенията на простите числа са наистина интересни, но нека да преминем към задачата.

Вашата задача е да намерите броя на простите числа в зададен интервал [A, B]. За числата А и В е вярно, че 1.10⁶ <= A < B <= 4.10⁹. Разбира се, Вашата програма трябва да работи задоволително бързо. При тези строги условия е нормално да се допуснат малки грешки при изчисленията. Ето защо за верни отговори ще се приемат отговори, които са с отклонение до 0.1% от верния отговор. Например ако в зададен интервал имаме 1000 прости числа, то за верни ще се приемат отговорите 999, 1000 и 1001.

Име на входния файл: PRIME.INP
Описание на входния файл:
Входният файл съдържа няколко интервала, за всеки от които трябва да се намери броя на простите числа в него. Всеки интервал се задава на отделен ред с две числа А и В разделени с интервал. Входният файл завършва с един ред съдържащ две нули разделени с интервал - "0 0".

Име на изходния файл: PRIME.OUT
Описание на изходния файл:
Изходният файл трябва да съдържа по един ред за всеки интервал, като на този ред трябва да е записан броя на простите числа в интервала. Последователността на редовете в изходния файл трябва да съответства на последователността на интервалите от входния файл.

Примерен входен файл:
10002000 10003000
100200300 100300300
0 0

Изходен файл за примерния входен файл:
66
5431