Prime Number Algorithms with R.

By
I've recently been read up on prime number theory, which has inspired me to investigate some prime number algorithms myself.

First of all, the most obvious way to solve for prime numbers is the brute force method.   I.e if you are evaluating whether a number (n) is prime, check if it can be factorized by integers from 2 to n-1.  If not, then it is a prime.  Needless to say, this is the most inefficient method of finding prime numbers.

A more efficient algorithm for finding primes is the Sieve of Eratosthenes.  The way that it works is very intuitive.  You basically only evaluate primality on numbers less than the square root of n, which allows you to rule out all multiples of those prime numbers.  After you have done this, what you are left with is only the prime numbers up to the number n.

So why only up to the square root of n?  How can you be sure that integers above the square root of n are prime numbers if you don't check them individually?

The explanation is quite intuitive:

Suppose you are evaluating primes up to 100.  The square root of 100 is 10, so you would only need to rule out multiples of numbers up to 10.   Say the number "37" is left over, and you are skeptical of whether it is indeed a prime.  If 37 wasn't a prime, then it would be a multiple of 2 or more prime numbers, of which one has to be a prime less than 10  (Since two numbers greater than 10 multiplied would be > 100).  However, you have already ruled out multiples of primes less than ten, so "37" must be a prime!

Here is an animation of the sieve in action:


As you can see, it is much more efficient than the brute force method which requires all numbers to be evaluated individually for primality.

Here is the code that I wrote in R to replicate the Sieve of Eratosthenes (O(sqrt(n)). 

test <- function(x) {
 primes <- matrix(c(rep(1,x),c(1:x)),ncol=2) # generate a table with a column of 1's and a column of consecutive integers
 primes[1,1]<-0                              # mark the number 1 as not being prime
 for (n in primes[seq(1,floor(sqrt(x)),1),2]) {        # for the values from 1 to x...
  if (primes[n,1]==1) {       # if the number hasn't been marked as prime yet...
   primes[seq.int(2*n,x,n),1]<-0       # mark all multiples of that number as not prime
  }
 }
 return(primes)                            # all numbers left over are prime
}



In contrast, here is code that I wrote using the brute force method.  O(n), much less efficient

findprime <- function(x) {
 k = 0 
 y = c(1:x) #define a set of integers from 1 to x
 for (n in y) {
  if (x %% n == 0) k<-k+1  #if the remainder is not 0, then add 1 to k
 }
 if (k==2) return(c("yes",k)) #if prime, then only 2 numbers should have remained 0 (1 and x), otherwise the number is not prime 
 else if (k!=2) return(c("no",k))
}

Ill update this post further as I learn more prime algorithms!

Comments

Post a Comment

Popular posts from this blog

grandmaster level chess AI using python - Part 2 (the code)

By
Image
In continuation of part 1, I will now building my chess AI in python.  As mentioned before, my goal is to create a chess AI at the Grandmaster level (elo > 2500) Here is the code for the chess AI. https://github.com/luweizhang/chess_ai Key components of the chess game / AI: Python Classes: ChessGame instantiates the chessboard and pieces keeps track of whose turn it is RulesEnforcer Logic for how all the pieces move, castling Makes sure you cant make illegal moves Used in the chess AI to generation possible positions ChessAi Tree generator generates the tree of position moves Position Evaluator evaluates the quality of chess positions Minimax Determines the optimum move from the chess tree ChessDB Opening database Explanation of the tree generator: The tree generator component of the chess AI generates the possible future board positions based on the possible moves that the pieces can make.  At any given position, there are o...
Read more

building a chess ai - part 4: learning an evaluation function using deep learning (keras)

By
Image
Note: this post is still in progress. Below I will discuss approaches for training a deep learning chess game and the results of my implementation. Approach 1: Train against the outcome of the game *y* is the outcome of the game (1 is win for white, 0 is loss for white, .5 is draw) We want to learn a function * f(p)* that can approximate this. *p*  is the chess position (8x8 chess board), actually is an 8x8x12 = 768 dimensional vector (since there are 12 pieces)      8x8x6  = 384 dimensional vector with positive values for squares with a white piece and negative values for squares with a black piece.  (Using 64 x 12 introduces too many degrees of freedom) The goal is to try to learn a function * f(p)* that can predict the winner of the game * y* given a chess position * p* . The model: Dataset: http://www.ficsgames.org/download.html millions of high quality games played by grand masters or international masters Objective/Loss Function...
Read more

Brief intro to recurrent neural networks

By
Image
Note: This post is meant to be a brief and intuitive summary of recurrent neural networks.   I have adapted this material from the Coursera deep learning course.  The value I hope to add here is that I have attempted to summarize the information in a way that is easy (hopefully) to understand, and can be used as reference or refresher material for the future. Part 1: Recurrent Neural Networks: Recurrent neural networks are a class of neural networks where the nodes/neurons form a directed graph along a sequence.  They are very effective at tasks such as Natural Language Processing because they have a "memory," in other words they can receive context from previous inputs.  They can take in input one at a time, and can pass information from one node to the next via hidden activation layers.  This information serves as the "memory" or "context" layer of the network, which can be used in conjunction as more new input is being processed. RNN Cell: ...
Read more