Write an algorithm to return the prime numbers of an integer, for example if your input is 10 the output is list a with elements 2 and 5

Question

this one i get as assignment in discrete maths. i try to do like this.

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

Answer 1

What you are looking for is called "prime number factorisation".

On http://www.btinternet.com/~se16/js/factor.htm you find an example in 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
     }`enter code here`

Answer 3

If you can generate prime numbers, you can do prime factorization. The only trouble is that it's unavoidably slow.

A simple way is to use the traditional seive of eratosthenes to generate the prime numbers. For each prime generated (in increasing order), repeatedly check whether it divides your number. Each time it does, accept it as a factor and replace your number with the result from the division. When you can't divide any more, move on to the next prime.

So if your number were 20, you'd first try prime 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

When you reduce your remaining number to 1, you end.

Answer 4

Finding the prime factors of a given number is a hard problem. When the numbers are very large, no efficient factorization algorithm is known. But here's a simple algorithm to find the prime factors of a relatively small number N:

1. list all the prime numbers in the range 2...N.

2. for each prime number p in the list, check if N mod p is 0. If so, p is a (prime) factor of N.

How to list all the prime numbers in the range 2...N?

We'll start with an empty list and fill it with prime numbers:

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

Note that this is a very simple algorithm and there are many algorithms which are much better. If you need a more clever solution check out Dixon's algorithm or the Quadratic Sieve algorithm.

A better (but less triavial) way to list all the prime numbers up to N is the Sieve of Eratosthenes.

Some bugs in your algorithm:

1. You probably meant to write "n mod i = 0", not "n mod i = 1". "n mod i = 0" is equivalen to "n is divisible by i" or "i is a factor of n".
2. What your algorithm finds is all the factors of n while what you need to find is all the prime factors of n.