Напишите алгоритм для возвращения простых чисел целого числа, например, если ваш вход равен 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

//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 
    } 

Answer 3

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

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

Так что, если ваш номер был 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

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

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

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

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

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

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

Обратите внимание, что это очень простой алгоритм и существует множество алгоритмов, которые гораздо лучше. Если вам нужно более умное решение, проверьте Dixon's algorithm или Quadratic Sieve algorithm.

Лучше (но менее triavial) способ перечислить все простые числа до N - это Sieve of Eratosthenes.

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

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