It looks like you're new here. If you want to get involved, click one of these buttons!

- 141.1K All Categories
- 103.8K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 551 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 93 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 745 Computer Hardware
- 3.5K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 199 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 604 Jobs Wanted
- 211 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 7 Join the Team
- 356 Comments on this site
- 70 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 639 Off topic board
- 220 Mobile & Wireless
- 92 Android
- 126 Palm Pilot
- 340 Multimedia
- 156 Demo programming
- 184 MP3 programming
- Bash scripts
- 27 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 371 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 943 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 270 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 6 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 309 WEB Servers
- 156 WEB-Services / SOAP

Chandan Thour
Member Posts: **20**

in C and C++

What is the most optimum method of finding a prime number?

Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.

Kindly tell the most efficient method of finidng a prime number.

Post the code or link to it.]

Regards

chandan

Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.

Kindly tell the most efficient method of finidng a prime number.

Post the code or link to it.]

Regards

chandan

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven

© 1997-2017 Programmersheaven.com - All rights reserved.

## Comments

117: Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.

: Kindly tell the most efficient method of finidng a prime number.

: Post the code or link to it.]

:

: Regards

: chandan

:

You can at least skip every second number since it is even and not prime. If you manage to deduce a formula of which the result is always a prime number, a math institute apparently will pay you one million dollars. I cant remember their name now.

1,784: : Till we use a method of incrimenting a number and then dividing it with all the preceding numbers.

: : Kindly tell the most efficient method of finidng a prime number.

: : Post the code or link to it.]

: :

: : Regards

: : chandan

: :

:

:

: You can at least skip every second number since it is even and not prime. If you manage to deduce a formula of which the result is always a prime number, a math institute apparently will pay you one million dollars. I cant remember their name now.

:

This is one of the unsolved problems of mathematics.

One way to speed up the algorithm is to do like this:

[code]

do forever

a++

b=1

do

inc b

until b = a OR (a mod b) > 0

if b = a, it's a prime

else it's not

[/code]

Or even faster in assembler:

[code]

start:

inc ax

xor bx,bx

inc bx

loopstart:

inc bx

cmp ax,bx

je prime

mov cx,ax

mod cx,bx

jnz notprime

jmp loopstart

prime:

print "It's prime" ;OK, I don't got the time to write all the memmory.

jmp start

notprime:

print "It's not prime"

jmp start

[/code]

I wrote it in psuedo asm, I don't got time right now to write it in real asm.

[b]Niklas Ulvinge[/b] [white]aka [b]IDK[/b][/white]

2,444To speed it up a bit more, the following two hints:

1. To check if a number is prime you only need to divide it by 2 to the square root of that number, including the square root.

2. Actually, but this is only faster if you're creating a row of primes, you only need to try and divide the number by every prime number that is between 2 and it's square root. But like I said, for a single number this is rarely faster.

And another remark:

For checking a row of number for primality, you could also use "The Sieve of Erasthotenes". Might be worth checking out if you're interested ;-)

Greets...

Richard