Задача:
Пусть R — разность максимального и минимального простых делителей целого числа, не считая самого числа.
Напишите программу, которая перебирает целые числа, большие 3 333 337 в порядке возрастания и ищет среди них такие, для которых R больше 1000 и кратно 3.
Запишите первые 5 чисел в порядке возрастания в первом столбце, во втором — соответствующие значения R.
Код:
using static System.Math;
class MAIN
{
public class Simple_Dividers
{
List<int> simple_dividers = new List<int>(new int[] {2, 3}); //Список простых чисел
public List<int> ShowSimpleDividers
{
get
{
return simple_dividers;
}
}
public bool IsSimple(int n) //Проверка числа на простоту; добавление его и всех простых чисел меньше его в simple_dividers
{
if (n < simple_dividers[simple_dividers.Count - 1] && simple_dividers.Contains(n)) return true;
foreach (int div in simple_dividers) if (n % div == 0) return false;
for (int poss_div = simple_dividers[simple_dividers.Count - 1] + 2; poss_div < n; poss_div += 2) if (this.IsSimple(poss_div)) if (n % poss_div == 0) return false;
simple_dividers.Add(n);
return true;
}
public int GetR(int input) //Собственно, основной метод (решение). Возвращает R, если число подходит, и -1, если число не подходит
{
double square = Sqrt(input);
int min_div = -1;
int max_div = -1;
foreach (int div in simple_dividers) //Поиск наименьшего простого делителя в списке
{
if (input % div == 0)
{
min_div = div;
break;
}
}
if (min_div == -1) //Поиск наименьшего простого делителя вне списка
{
for (int poss_div = simple_dividers[simple_dividers.Count - 1] + 2; poss_div < square; poss_div += 2) if (this.IsSimple(poss_div)) if (input % poss_div == 0) { min_div = poss_div; break; }
}
if (min_div == -1) return -1;
int min_max_div = min_div + 1002; //Значение, меньше которого не может быть максимальный простой делитель
for (int i = simple_dividers.IndexOf(min_div) + 1; i < simple_dividers.Count; i++) //Проверка, есть ли максимальный простой делитель в списке простых делителей
{
if (simple_dividers[i] >= min_max_div)
{
if (((simple_dividers[i] - min_div) % 3 == 0) && (input % simple_dividers[i] == 0)) max_div = simple_dividers[i];
}
}
if (max_div == -1) { for (int poss_max_div = min_div + 1002; poss_max_div < input; poss_max_div += 3) if (input % poss_max_div == 0) if (this.IsSimple(poss_max_div)) max_div = poss_max_div; } //Грубый поиск на случай, если максимального простого делителя нет в списке
else //Для гарантии, что нет простых делителей больше
{
for (int poss_max_div = max_div + 3; poss_max_div < input; poss_max_div += 3) if (input % poss_max_div == 0) if (this.IsSimple(poss_max_div)) max_div = poss_max_div;
}
return max_div == -1 ? -1 : max_div - min_div;
}
}
static void Main()
{
Simple_Dividers tester = new Simple_Dividers();
int R;
for (int i = 3_333_337, count = 0; count < 5; i++)
{
R = tester.GetR(i);
if (R != -1)
{
Console.WriteLine($"{i} {R}");
count++;
}
}
}
}
Вместо нужного
- 3333338 9309
- 33333340 166665
- 3333342 555555
- 3333349 2748
- 3333354 1287
программа выводит
- 3333337 15354
- 3333338 9309
- 3333340 166665
- 3333342 555555
- 3333349 2748
Что тут не так? В чём ошибка?
Простой
