Самый простой способ (как мне видится): делаем массив простых чисел, генерируем случайное число в пределах длины массива и вынимаем простое число по полученному индексу. Из минусов - потеря времени на формирование массива если это делать руками, но никто не запрещает написать утилитку, которая будет генерировать массив требуемой длины.