45807

How to detect a prime

Question:

I know that there are many binary operations to show that something is true for example we can show if number is power of two or something else is there some theory or special binary method to show if number is prime?

Answer1:

Detecting if a number is prime is not very easy!

Read this article about the <a href="http://www.cse.iitk.ac.in/~manindra/algebra/primality_v6.pdf" rel="nofollow">PRIMES is in P</a> breakthrough: <a href="http://www.ams.org/notices/200305/fea-bornemann.pdf" rel="nofollow">http://www.ams.org/notices/200305/fea-bornemann.pdf</a> to give you an idea of how tough a problem this actually is.

This news article might be an easier read: <a href="http://members.cox.net/mathmistakes/primes.htm" rel="nofollow">http://members.cox.net/mathmistakes/primes.htm</a>

In short, if you find a simple 'binary method' you will be famous!

Answer2:

Generally you just <a href="http://en.wikipedia.org/wiki/Primality_test" rel="nofollow">check</a>.

Answer3:

For a good example of a Sieve algorithm for finding primes you can check our this wikipedia page.

<a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow" title="Sieve of Eratosthenes">Sieve of Eratosthenes</a>

One of the more interesting methods for finding primes, and the Euler Sieve (touched upon at the bottom of the same page) speeds it up a little.

Answer4:

There is really big difference between decting power of 2 and prime numbers.<br /> If you'll look at our system of number representation: 1243 = 1*10<sup>3</sup> + 2*10<sup>2</sup> + 4*10<sup>1</sup> + 3*10<sup>0</sup><br /> It's pretty easy to determine when number can be divided by 10 (lowest digit is zero) or is power of 10 (all lowest digits is zero and highes it "1", or sum of all digits equals to 1).<br /> The same for binary: 1243 = 1*2<sup>10</sup> + 0*2<sup>9</sup> + 0*2<sup>8</sup> + 1*2<sup>7</sup> + 1*2<sup>6</sup> + 0*2<sup>5</sup> + 1*2<sup>4</sup> + 1*2<sup>3</sup> + 0*2<sup>2</sup> + 1*2<sup>1</sup> + 1*2<sup>0</sup><br /> You can check digits to check if number can be divided by 2 or even is power of 2 in the same way as for 10-based number representation.

Now consider other systems of numbers representation. I guess Roman numerals should have some interesting properties also, but you probably interested in something like: 1243 = 2<sup>0</sup> * 3<sup>0</sup> * 5<sup>0</sup> * 7<sup>0</sup> * 11<sup>1</sup> * 13<sup>0</sup> * 17<sup>0</sup> * 19<sup>0</sup> * 23<sup>0</sup> * 29<sup>0</sup> * 31<sup>0</sup> * 37<sup>0</sup> * 41<sup>0</sup> * 43<sup>0</sup> * 47<sup>0</sup> * 53<sup>0</sup> * 59<sup>0</sup> * 61<sup>0</sup> * 67<sup>0</sup> * 71<sup>0</sup> * 73<sup>0</sup> * 79<sup>0</sup> * 83<sup>0</sup> * 89<sup>0</sup> * 97<sup>0</sup> * 101<sup>0</sup> * 103<sup>0</sup> * 107<sup>0</sup> * 109<sup>0</sup> * 113<sup>1</sup> = 11<sup>1</sup> * 113<sup>1</sup> = [0,0,0,0,1,0,0,0,0,0...]<sub>prime-based</sub><br /> I.e. number is encoded as product of powers of prime numbers. Such system have nice property of doing different prime-related checks much easier than in bits or in decimals.

P.S. While systems with weighted-sum gives you easy way to calculate sums and difference, systems with powered product simplifies multiplication and division.

Answer5:

bool isPrime(int number){ if(number < 2) return false; if(number == 2) return true; if(number % 2 == 0) return false; for(int i=3; (i*i)<=number; i+=2){ if(number % i == 0 ) return false; } return true; }

Notice. It will be slow if your input more than 10^9.

Recommend

  • Run long process continously using Tkinter (Python 2.7)
  • Terminating generator expression [duplicate]
  • Print every prime number before N number
  • Prime numbers using Sieve of Atkin with BigInteger
  • Does pImpl fundamentally solve C++ DLL issue?
  • How to activate JS data-filter when page loads?
  • How should I start to implement RESTful web service?
  • Exception handling as per java coding standards
  • Whats the right place for testhelper-classes? (phpunit/best practise)
  • SQL query to group by maximal sets of a column having inner consecutive distances below a threshold
  • How do I signal completion of my dataflow?
  • Convert Type Decimal to Hex (string) in .NET 3.5
  • Unable to install Git-core+svn by MacPorts
  • Calling Worksheet functions from vba in foreign language versions of Excel
  • Django simple Captcha “No module named fields” error
  • Parsing a CSV string while ignoring commas inside the individual columns
  • MailKit: The IMAP server replied to the 'EXAMINE' command with a 'BAD' response
  • Could not find rake using whenever rails
  • Avoid links criss cross / overlap in d3.js using force layout
  • Jenkins: How To Build multiple projects from a TFS repository?
  • Nant, Vault & Windows Integrated Authentication
  • Regex thinks I'm nesting, but I'm not
  • Fetching methods from BroadcastReceiver to update UI
  • Bug in WPF DataGrid
  • Get object from AWS S3 as a stream
  • TFS: Get latest causes slow project reloading
  • Controls, properties, events and timers running in design time
  • Cross-Platform Protobuf Serialization
  • Validaiting emails with Net.Mail MailAddress
  • Running a C# exe file
  • Join two tables and save into third-sql
  • How to model a transition system with SPIN
  • ORA-29908: missing primary invocation for ancillary operator
  • Do I've to free mysql result after storing it?
  • Can Visual Studio XAML designer handle font family names with spaces as a resource?
  • How can I remove ASP.NET Designer.cs files?
  • python draw pie shapes with colour filled
  • Is there any way to bind data to data.frame by some index?
  • How can i traverse a binary tree from right to left in java?
  • Converting MP3 duration time