Find prime numbers from a given number

[gchiazx]

Hi, can someone send me the algorithm for finding the products of prime numbers from a given number?

Thank You

Gary.

[arne]

Hi, can someone send me the algorithm for finding the products of prime numbers from a given number?

Thank You

Gary.

One possible algorithm would work like this:

start with d = 2 and num = given number
repeat
   check if your num is divisible by d
   if yes
        print out d and divide num by d
   if no
        increase d by one
while ( d is smaller than half the given number and num is unequal 1 ) 
 

[Banfa]

start with d = 2 and num = given number
repeat
   check if your num is divisible by d
   if yes
        print out d and divide num by d
   if no
        increase d by one
while ( d is smaller than half the given number and num is unequal 1 ) 
 

This routine could be optomised to in the following ways to run faster

1. Take account of 2 being the only even prime number, don't bother checking 4, 6, 8 etc.

2. Change while condition to

while ( d is smaller than the square root of the given number and num is unequal 1 )

If the stop condition is (d is greater than the square root of the given number) rather than (num is equal 1) the num will be unequal 1 and will be a prime divisor of the given num. (Try with the input 15)

3. This algorithm tests all numbers, if the given number is very large and has at least 1 large prime divisor then it will be in efficient because it will be testing lots of non-prime numbers that can not possible be prime divisors of the given number.



I wonder but don't know if this may be more efficient

FUNCTION GetPrimeDivisors( Number )
 
  Test = The Square Root Of Number
 
  WHILE(Test Not Equal To 1)
    CHECK if your number is divisible by Test
 
    IF yes 
      end loop
    ELSE IF no
      test = test - 1
    END IF
  END WHILE
 
  IF Test Equal To 1
    Print Number
  ELSE IF Test Not Equal To 1
    CALL GetPrimeDivisors( Test )
    CALL GetPrimeDivisors( Number/Test )
  END IF
END FUNCTION
 

Hmm think I will just make sure this works

[Banfa]

Well it does work but I still have no idea how efficient it is or isn't

[mukesh verma]

check a prime number program written in c language ............
<code snipped>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////
hi My name is mukesh, i am red tech web devloper, well red tech is a group of IT engineers, For any query related to programming write at us : <email snipped> or <email snipped>. our web site providing a large collection of programs but write now its under construction. plz keep visiting this site.
<web address snipped>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

[Savage]

Hi, mukesh would u please read posting guidelines and especialy the part How to Respond to a Question.


Savage

[Savage]

Well it does work but I still have no idea how efficient it is or isn't

I do think this will be even more efficient:

for(first counter starts with num;first counter>=3,which is first prime;firstcounte--)
{
    //Here we need some type of pointer if it's 0 then number is a prime e.g 
      test=0
 
      for(sec counter=2;sec counter<first counter;sec counter++) if moduo of 
      first counter and secound counter is 0, test=1;
 
      if test is 0 output the number;
 
}

Savage

[Ganon11]

I wonder but don't know if this may be more efficient

FUNCTION GetPrimeDivisors( Number )
 
  Test = The Square Root Of Number
 
  WHILE(Test Not Equal To 1)
    CHECK if your number is divisible by Test
 
    IF yes 
      end loop
    ELSE IF no
      test = test - 1
    END IF
  END WHILE
 
  IF Test Equal To 1
    Print Number
  ELSE IF Test Not Equal To 1
    CALL GetPrimeDivisors( Test )
    CALL GetPrimeDivisors( Number/Test )
  END IF
END FUNCTION
 

Erm...does it work?

Test starts as the square root of a number, and then you test that Test != 1. The only change you are making to Test is Test -= 1. (actually, you write test = test - 1...same thing functionally). Suppose Number is not a perfect square, like 15. Then the square root of Number is some decimal (here, between 3 and 4), and will never equal 1.

Unless you're depending on the square root operation to truncate Test to an integer...

[JosAH]

Except for 2 and 3 you only have to test for multiples of 6 plus or minus 1.
Until a potential divisor squared is larger than the number to be tested.

kind regards,

Jos

[Banfa]

Unless you're depending on the square root operation to truncate Test to an integer...

OK just wait 6 months and _then_ pick at my pseudo code :p

Actually since divisor have to be integers I was assuming integer arithmatic in the routine but I should have stated it.

[Banfa]

Except for 2 and 3 you only have to test for multiples of 6 plus or minus 1.
Until a potential divisor squared is larger than the number to be tested.

Or alternitively put you can skip every 3rd odd number because it is bound to be divisible by 3, and all even numbers because they are divisible by 2.

The question is can you code that efficiently (to which actually I think the answer is probably yes if you code it in the terms you have already given).

[JosAH]

Or alternitively put you can skip every 3rd odd number because it is bound to be divisible by 3, and all even numbers because they are divisible by 2.

The question is can you code that efficiently (to which actually I think the answer is probably yes if you code it in the terms you have already given).

Yup, except for 2 and 3 you can do something like this:

for (int d= 5, inc= 2; d*d <= n; )
   if (n%d == 0) // d is a factor
      n/= d; // if you want to find all factors;
   else {
      d+= inc; // next possible divisor
      inc= 6-inc; // next increment
   }

kind regards,

Jos