Hi, can someone send me the algorithm for finding the products of prime numbers from a given number?
Thank You
Gary.
11 46443 arne 315
Recognized Expert Contributor
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 9,065
Recognized Expert Moderator Expert 
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 nonprime 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 9,065
Recognized Expert Moderator Expert
Well it does work but I still have no idea how efficient it is or isn't
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 1,764
Recognized Expert Top Contributor
Hi, mukesh would u please read posting guidelines and especialy the part How to Respond to a Question.
Savage
Savage 1,764
Recognized Expert Top Contributor
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 3,652
Recognized Expert Specialist
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 11,448
Recognized Expert MVP
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 9,065
Recognized Expert Moderator Expert
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.
Sign in to post your reply or Sign up for a free account.
Similar topics 
by: Dag 
last post by:
Is there a python module that includes functions for working with prime
numbers? I mainly need A function that returns the Nth prime number and
that returns how many prime numbers are less than N, but a prime number
tester would also be nice. I'm dealing with numbers in the 10^610^8 range
so it would have to fairly efficient
Dag

by: Greg Brunet 
last post by:
In doing some testing of different but simple algorithms for getting a
list of prime numbers, I ended up getting some results that seem a bit
contradictory. Given the following test program (testPrimes.py) with
two algorithms that both check for primes by testing only odd numbers
using factors up to the square root of the value, where Primes1 is based
on all of the existing primes so far, and Primes2 is based on all odd
numbers, I would...

by: rhle.freak 
last post by:
Here is my code to generate prime numbers.It works absolutely fine when
the range is
*not very large*. However on initializing i with a large integer it
produces erroneous results
(some numbers ending in 5 ..which obviously cannot be prime numbers)
can anyone please help me out with the reason??
/*Generate Prime Numbers*/
#include<stdio.h>

by: newstips6706 
last post by:
1, 2, 3, 5, 7... PRIME Numbers
________________________________
Definitions
What is a PRIME Number ?

by: Caffiend 
last post by:
Thanks to everyone who helped me out with my early version of the prime number calculator... Here is the complete and updated version including unsigned 64 bit integers...mmmmmm....... Lots of fun with the higher numbers, but my humble 1.86 gHz centrino with 1gb RAM slows to a crawl with numbers in excess of a billion or ten.... :) Here is the complete program, if you want to have some fun with it:
#include <iostream>
#include <math.h>...
 
by: Caffiend 
last post by:
Well, I've been picking at learning python, got tired of reading, and figured I'd try to replicate my prime number generator I wrote (with much TSDN forum help) in C++. I've hit a stumbling block... the program is supposed to print onscreen all the prime numbers between two numbers given to it, so if I put in 1 and 10, it should print out 1, 3, 5, 7 (I know, technically 1 isn't considered prime, and 2 should be on there, but otherwise...) ...

by: cnixuser 
last post by:
Hello, I am attempting to create a prime number detector that will identify all of the prime numbers within a specified range of numbers. The problem is, for some reason my program is not detecting any prime numbers and seems to be only to be printing one value of zero from the array that I am trying to store the prime numbers detected in. I believe the zero is coming from the value already stored in the array when I initialzed it, which means...

by: ace2606 
last post by:
Hi
I am a beginner in C++ and would like someone to give me an idea or push me in the right direction of how to solve this question , It is related to classes
Design and implement a class called PrimeChecker to check if a number is
prime. The class stores an array of consecutive primes. It uses this array
to check if a given number is prime. To simplyfy the excercise the array
will store at most 1000 prime numbers. The class has the...

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...

by: Hystou 
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...

by: Oralloy 
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bitfields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++12 std=c++20 Wnarrowing bit_field.cpp
Here is the code in...
 
by: Hystou 
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...

by: isladogs 
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...

by: conductexam 
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 