Fastest way to check whether a given number is prime/Semi Prime

Below is my first discovery in the world of prime numbers:

 
Problem statement

A semi prime (also called biprime or 2-almost prime, or pq number) is a natural number that is the product of two (not necessarily distinct) prime numbers(Source:Wikipedia)

The only way to check whether a given number is prime with 100% probability is finding whether the given number has factors when you iterate between the value “2” and square root of the given number.

The same number of iterations are used to determine whether a given number is semi-prime.

Solution

With 100% probability we can check whether a given number is prime/semi-prime, with very very less time complexity.

Below is the process to follow:

1.       Find the cube root of the given number(let’s say this as “n”). Let’s say the cube root is “cn”

2.       Make a list of all the prime numbers till the prime number which is greater than “cn”, but is the least. So if “cn” is “4”, we need to take prime numbers till “5”.

3.       Check any of the prime number in step-2 divides “n”. If yes, then the “n” is neither prime nor semi-prime

4.       If we exhaust all the prime numbers in step-2 and still nothing divides “n”, then “n” is prime or semi-prime

Example

Let’s say we take any number below 10,000 and want to confirm whether it is prime/semi-prime/none.

Cuberoot of 10,000 is 21.544. Rounding off to nearest integer it is 22.

Take the prime numbers till 23(which is the least prime number that is greater than cuberoot of number we want to determine) and see if any of these divides our number. If nothing is able to divide then our number is prime/semi-prime.

In python the implementation will be as below, if we consider first 10,000 positive integers(note the array is initialized to first 9 prime numbers). Any of the first 10,000 positive integers can be evaluated to be prime/semi-prime using the below function. For numbers greater than 10,000 we just need to increment “arr” array.

Impact

Below are some of the possible applications for this solution:

1.       To check whether a given number is prime/not requires exponential time complexity as the number grows big. Although our solution results in Semi-primes along with primes, this helps in narrowing down quickly whether the number is not a prime.

2.       Semi-primes are used in RSA algorithm where the multiple of two large primes is used for modulus.

3.       Other applications that use large prime numbers in cyber security

Compared this with miller-rabin test with first 50,000 positive integers and the results generated are the same. Used 40 iterations for miller-rabin test which is minimum required to get good probability for Miller-rabin.

Although the results generated are same with Miller-rabin, the time taken to check whether the given number is prime/Semi-prime and print them with my solution is nearly half. Below are the times in a 1.6 GHZ clockspeed Ubuntu M/c.

	Miller-Rabin(In seconds)	Proposed Solution(In Seconds)
Real	0.497	0.227
User	0.188	0.183
Sys	0.026	0.025

Installing tensorflow in windows easily

Before installing Tensorflow, first install python in your machine.

Use this link to download and install latest Python 3.6.2. This will automatically install Python, PIP and set environment variables. Don't mess with the default settings here.
https://www.python.org/ftp/python/3.6.2/python-3.6.2-amd64.exe

First install Microsoft Visual C++ Redistributable 2015 x64

Type CMD in windows search bar and right-click run as administrator.

Then you need to run the below command

C:\> pip3 install --upgrade tensorflow

Now, tensor flow is installed in your computer. To verify the installation of tensorflow, in the same terminal run python and then below:

>>> import tensorflow as tf

>>> hello = tf.constant('Hello, TensorFlow!')
>>> sess = tf.Session()
>>> print(sess.run(hello))

If there is no error and you see below output, then tensor flow installation is successful.

Hello, TensorFlow!

If you see error like AVX support not there, follow 

Uninstall existing tensorflow using "pip uninstall tensorflow", then reinstall it using "pip install <Path to downloaded WHL file>". Download this WHL file into your computer - github.com/fo40225/tensorflow-windows-wheel/blob/master/1.10.0/… , if you have a 3.6 Python and a 64-bit windows(ignore the amd you see). Otherwise navigate a step back in github and search for correct WHL. It works

Understanding futures in stock market

Let us know talk about futures. Please complete going through the previous post on derivatives before reading this. What are futures? As you already know, futures are a kind of derivatives, whose value most closely resembles the price of the underlying stock.

For example, consider an RCOM stock. Futures have an expiry date, which is usually the last Thursday of the month. Today's date is 26th June, so we we have a 29th June derivative of RCOM which expires on 29 June and whose value is closely resembles the underlying stock. Below is a snapshot taken from the NSE website of 29th June future.


As you can see the closing price of the derivative on Friday at the market closing hours is Rs. 21.4. Now let's see the underlying stock RCOM closing price on the same day when the market closed which is as below.


As you can see the values are a close resemblance of each other. Also if you see their intraday chart which is a graph in the bottom right corner of both, you can observe both have almost same moment except the price point. This gives you a glimpse of future, and at any particular day if you can predict the movement of the stock you can buy its derivative and make good money even though you have around less than 20000 rupees in your account. Sometimes you can even get an almost equal amount of money as profit, that is the power of futures.

Now take a look at the derivative snap which I posted again by scrolling above. As you can see the derivative opened at 20.5 it reached an intraday high of 21.8 and intraday low of 19.9. This means as you can just see in the intraday chart, at different times of the day the derivative keep moving. Now, just consider you bought the derivative of RCOM when the derivative price is trading at 20.2. You know for sure that RCOM is trying to sell Assets and that is positive for the stock. So since the stock goes up, it means this future also will go up. So, as per  RCOM leverage rules, you can buy 12000 shares of RCOM future for about 16000 rupees. And it is mandatory that whatever you buy it has to be in multiple of 12000. Now you have invested your 16000 rupees in the morning by buying 12000 shares of rcom derivative at price rupees 20.2. Now wait till evening when the price reaches to do 21.2 and sell it off so you can see that you have a 1 Rupee profit per share. This can be automated, where you can put target at 21.2, and keep doing your other work also as all stock broking accounts now offer this feature. At around 2 PM your target is reached. Now, if you multiply 1 rupee profit per share with 12000 shares you got this 12000 rupees. So you can see the power of futures, in giving you the maximum value for your money invested at the same time even if you don't have the high amount of money to buy 12000 stocks. Isn't it great.

But there is a downside also. If the stock after you bought it for 20.2, would have gone to 19.2 you would have made a loss of 12000 rupees. So you must be cautious enough while buying the derivatives that you try to get it when you are buying for as low price as possible and when you are selling don't be greedy that it will reach more highs. Keep a target for your profits too. We will discuss about options in my next post.