Javascript-форум - Рекурсия

Javascript-форум (https://javascript.ru/forum/)

- Общие вопросы Javascript (https://javascript.ru/forum/misc/)

- - Рекурсия - JavaScrit (https://javascript.ru/forum/misc/67330-rekursiya-javascrit.html)

DivMan,

function foo(chislo){
  while(true){
  	if(chislo % 2 != 0){
  		return chislo + ' Простое число';
  	}
    else{
    	return foo(chislo + 1);
    }
  }
}

alert(foo(25));

5 * 5 = 25!!!

Цитата:

Просто́е число́ — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя

Я не знаю, как сделать условие

DivMan,
вариант без рекурсии, проверка числа на все возможные делители

function testPrime(number) {
    var isPrime = number == 2|| number == 3;
    var checkNumber = Math.sqrt(number);
        for (i = 2; i <= checkNumber; i++) {
        if (number % i == 0 && number != i) {
                isPrime = false;
                break
            } else isPrime = true;
        }

    return isPrime
}

alert(testPrime(23));

function IsPrime( N, M ) {
	M = M || Math.floor( N / 2 );
	return N % M == 0 ? false : M == 2 ? true : IsPrime( N, M - 1 );
}

alert( [IsPrime(22), IsPrime(23)] );

Diphenyl Oxalate,
отимальнее считать не c N / 2 а с квадратного корня числа.

function IsPrime( N, M ) {
  M = M || Math.sqrt(N)|0;
  return N % M == 0 ? false : M == 2 ? true : IsPrime( N, M - 1 );
}

alert( [IsPrime(22), IsPrime(23)] );

рони,
ваш алгоритм считает 2 и 3 за составные числа.

Оптимальнее проверять не все делители подряд от 2 до sqrt(N), а только простые делители. Например, если мы проверили делимость на 2, то нет необходимости проверять остальные числа кратные 2. (Т. е. нужно тогда проверить только 2, 3, 5, 7, 9, ..., sqrt(N) )

Можно уменьшить количество делителей предприняв тот же шаг для следующего простого числа -- 3. Тогда у нас останутся числа не кратные 2 и 3. (Теперь нужно проверить только 2, 3, 5, 7, 11, 13, 17, 19, ..., sqrt(N)) Легко заметить, что после 2 и 3 идут числа вида 6n ± 1

Т. е. после того как нашли наибольший делитель sqrt(N), необходимо его привести к виду 6n ± 1. Полученный делитель должен быть меньше либо равен sqrt(N).

function isPrime(number) {
  // простые числа 2 и 3
  if(number == 2 || number == 3)
	  return true;

  // определяем составные числа:
  // кратные 2 и 3 больше 1, остаются числа вида 6n ± 1, где n > 0, n ∈ Z
  if(number < 2 || number % 2 == 0 || number % 3 == 0)
	  return false;

  // steps[остаток от деления делителя на 6] == число, на которое увеличить делитель, чтобы получилось число вида 6n ± 1
  var steps = [-1, -2, -1, -2, -3, -4];

  // делитель приводим к виду 6n ± 1
  var i = Math.sqrt(number) | 0;
  var divider = (i - (i - 5) % 2 - 2 * (1 - Math.ceil(((1 + ((i - 5) / 2) | 0) % 3) / 2)));
  return isPrime(number, divider);

  function isPrime(number, divider) {
	  divider = divider;

	  // проверили все делители и пришли сюда?
	  // значит число простое
	  if(divider == 1) return true;

	  // после того как проверили делимость на 5,
	  // делаем вывод (на 2 и 3 нет смысла проверять,
	  // т. к. здесь могут быть только не кратные 2 и 3)
	  return number % divider == 0 ? false : divider == 5 ? true : isPrime(number, divider + steps[divider % 6]);
  }
}

alert([22, 23].map(function(v) {
	return v + " " + isPrime(v)
}).join("\n"));

Поскольку от 6n до 6(n + 1) только два числа не кратных 2 и 3, то на каждые 6 чисел из ряда 2, ..., sqrt(N) алгоритм выбирает 2 числа.
Это означает, что для проверки числа по этому алгоритму необходимо в 3 раза меньше делителей, чем в ряду 2, ..., sqrt(N)

Malleys,
Ваш код работает медленнее.
10к итераций за 50мс против 35мс у скрипта выше

Цитата:

Сообщение от Malleys

ваш алгоритм считает 2 и 3 за составные числа.

исправил
var isPrime = number == 1|| number == 3;
на 2
пост №13
если вы про код в №15 - то там да надо дополнить алгоритм

Цитата:

Сообщение от Diphenyl Oxalate

Ваш код работает медленнее.

Да, там достаточно ресурсо-затратное вычисление следующего кандидата на простое число. Особенно потому, что я пытался вычислять простые числа через рекурсию. Простые числа могут принадлежать множеству { 2, 3, 6n ± 1 }, где n > 0, n ∈ Z, и через цикл с шагом 6(а не с шагом 1, как в посте №13) оно же в 3 раза меньше чисел будет проверять, не так ли?

function isPrime(number) {
	if(number === 2 || number === 3)
		return true;

	var limit = 1 + Math.sqrt(number);

	if(number < 2 || number % 2 == 0 || number % 3 == 0)
		return false;

	for(var index = 6; index <= limit; index += 6) {
		if(number % (index - 1) === 0) return false;
		if(number % (index + 1) === 0) return false;
	}

	return true;
}

alert([22, 23].map(function(v) {
    return v + " " + isPrime(v)
}).join("\n"));