Напишите алгоритм, который будет возвращать простые числа целого числа, например, если ваш ввод равен 10, вывод представляет собой список a с элементами 2 и 5

Question

это я получаю как задание по дискретной математике. я пытаюсь сделать так.

procedure prime_numbers (x)
  n:= 1
  for i:= to n<=x do
    n mod i=1 then
      return (prime)
end prime_number.

Answer 1

То, что вы ищете, называется «факторизацией простых чисел».

На http://www.btinternet.com/~se16/js/factor.htm вы найдете пример в JavaScript.

Answer 2

Найти главные факторы для данного числа - сложная задача.Когда числа очень велики, эффективный алгоритм факторизации не известен.Но вот простой алгоритм поиска простых множителей относительно небольшого числа N:

1. перечислить все простые числа в диапазоне 2 ... N.

2. для каждого простого числа p в списке, проверьте, если N mod p равно 0. Если это так, p является (простым) множителем N.

Как составить списоквсе простые числа в диапазоне 2 ... N?

Мы начнем с пустого списка и заполним его простыми числами:

for n=2...N:
   foreach p in your list:
      if n mod p is 0 then continue
   insert n to the list

Обратите внимание, что это очень простой алгоритм, и есть много алгоритмов, которые намного лучше.Если вам нужно более умное решение, проверьте алгоритм Диксона или алгоритм квадратичного сита .

Лучший (но менее тривиальный) способ перечислить все простые числа вверхN - это Сито Эратосфена .

Некоторые ошибки в вашем алгоритме:

1. Вы, вероятно, хотели написать "n mod i = 0", а не "n mod i = 1 ".«n mod i = 0» эквивалентно «n делится на i» или «i является фактором n».
2. Ваш алгоритм находит все факторы n, в то время как вам нужно найтивсе простые факторы n.

Answer 3

Если вы можете сгенерировать простые числа, вы можете выполнить простое разложение. Единственная проблема в том, что это неизбежно медленно.

Простой способ - использовать традиционный набор эратосфенов для генерации простых чисел. Для каждого сгенерированного простого числа (в порядке возрастания) неоднократно проверяйте, делит ли оно ваше число. Каждый раз, когда это происходит, примите это как фактор и замените ваш номер результатом деления. Когда вы не можете больше делить, переходите к следующему штриху.

Итак, если бы ваш номер был 20, вы бы сначала попробовали простое число 2.

20/2 = 10, so accept factor 2 and use number 10
10/2 = 5, so accept factor 2 and use number 5
5/2  = 2 rem 1, so move onto prime 3
5/3  = 1 rem 2, so move onto prime 5
5/5  = 1, so accept factor 5 and use number 1

Когда вы уменьшаете оставшееся число до 1, вы заканчиваете.

Answer 4

//Copyright 1998 Henry Bottomley (written 23 December)
//All rights reserved

  function factorise(numm)                      // To calculate the prime factors of a number
     {
      var newnum = numm;                        // Initialise
      var newtext = "";
      var checker = 2;                          // First possible factor to check

      while (checker*checker <= newnum)         // See if it is worth looking further for factors 
         {      
          if (newnum % checker == 0)            // If the possible factor is indeed a factor...
             { 
              newtext = newtext + checker;      // ...then record the factor
              newnum = newnum/checker;          //    and divide by it
              if (newnum != 1)                  //    then check whether it is not last...
                 {
                  newtext = newtext + ".";      //    ...and if so prepare for the next
                 }
             }
          else                                  // otherwise...
             {
              checker++;                        // try the next possible factor
             }
         }
      if (newnum != 1)                          // If there is anything left at the end...
         {                                      // ...this must be the last prime factor
          newtext = newtext + newnum;           //    so it too should be recorded
         }
      if (newtext == "" + numm)                 // If the only prime factor is the original...
         {
          newtext = "Prime: " + newtext;        // ...then note that it must have been prime.
         }

      return newtext;                           // Return the prime factors
     }