Генерация случайного простого числа в C / C ++ между 2 пределами
Есть ли встроенная функция, которая может генерировать случайное простое число между 2 заданными пределами в C / C ++?
Я хочу функцию, которая может генерировать случайное простое число от 1 миллиона до 1 миллиарда
Решение
Вы можете сделать это эффективно так:
- Генерация случайного числа в этом интервале;
- Проверьте, делится ли оно на несколько первых простых чисел (скажем,
2 .. 17Эксперимент для лучших результатов). Если да, перейдите к 1; - использование Миллер-Рабин проверить на первичность.
Также см этот для похожей, немного более сложной идеи.
Другие решения
Когда мне пришлось это сделать, я создал функцию isPrime (). isPrime () проверит и определит, является ли число простым.
isPrime () имеет две разные функции, одна из которых будет работать вечно и печатать каждое простое число, а другая — до определенного числа.
Вы можете заполнить массив всеми простыми числами между i и j. Затем сгенерируйте случайное число, которое меньше или равно размеру массива. Используйте это случайное число, чтобы выбрать элемент из массива.
Надеюсь это поможет!
Чтобы сгенерировать случайное число между двумя границами, сделайте это
extern unsigned int urand();
int lower = 1000000;
int upper = 1000000000;
int p = urand() % (upper - lower) + lower;
Чтобы проверить, является ли число около 1 миллиарда простым, достаточно сделать пробное деление на все простые числа. < sqrt (1 миллиард) = 31622. Существует около 3400 таких простых чисел. Сделать массив
unsigned short primes[3400] = { 2, 3, 5, .. 31657 }
и разделить их всех. Если все пробные деления имеют остаток! = 0, то число простое.
Я сомневаюсь, что любой из более сложных тестов простоты будет быстрее для таких маленьких простых чисел.