Discussion Room : IDC101

Number of primes less than or equal to a given number, for a range of values

Number of primes less than or equal to a given number, for a range of values

by Ayushman Srivastava . -
Number of replies: 7

Today we had a task where we had to plot the number of primes less than or equal to a given number x, against x. Here’s a method which plots the graph for x = 10,000 instantaneously.

First, look at this table.

x

n = number of primes less than or equal to x

2

1

3

2

4

2

5

3

6

3

7

4

8

4

9

4

10

4

11

5

12

5

13

6

14

6

15

6

16

6

17

7

18

7

19

8

20

8

 

Notice anything? n increases only if the next value of x happens to be a prime.

So if n = 6 for x = 15, n will remain 6 for x = 16 because 16 is not a prime.

But n will increase by 1 for x = 17 because 17 is a prime.

So we need not define a function which checks for the number of primes less than or equal to an integer, and use that function in each iteration of the loop. We can simply add 1 whenever we encounter a prime, and append that value to a list. If the next number is not a prime, simply append the current value. We are storing these in a list because we want to use it to plot a graph.

 

def generateListForCountingPrimes(n):

    # The first element of the list l is the number of primes <= 2, the second element is the

    # number of primes <= 3 and so on

    l = [1]

    i = 3

    while i <= n:

        # Where prime(k) is a function which checks for primality

        if prime(i):

            l.append(l[-1] + 1)

        else:

            l.append(l[-1])

           

        i += 1

           

    return l

 

import numpy as np

import matplotlib.pyplot as pp

 

x = np.arange(2, 500001, 1)

y1 = generateListForCountingPrimes(500000)

y2 = [(i*1.0)/np.log(i) for i in x]

 

pp.plot(x, y1, x, y2)

 

pp.show()

In reply to Ayushman Srivastava .

Re: Number of primes less than or equal to a given number, for a range of values

by Gariman Singh -

Here is my program. The logic is same but is somewhat compact as I have not used functions.


import matplotlib.pyplot as p

import numpy as arr

n=10000

x=arr.arange(2,n+1,1)

s=0

y=[]

Y=[]

for i in x:

    a=0

    for j in range(2,i):

        if i%j==0:

            a=a+1

    if a==0:

        s=s+1

    y.append(s)

    Y.append(i/arr.log(i))

p.plot(x,y)

p.plot(x,Y)

p.show()



It took almost 12s to run on Jupyter but I want a faster program. Can anyone modify it.

In reply to Gariman Singh

Re: Number of primes less than or equal to a given number, for a range of values

by Ayushman Srivastava . -

The program I have posted is indeed faster; it generates the result for n = 10,000 instantaneously. 

I think you should cut-short the step in which you are checking for primality.

for i in x:

    a=0

    for j in range(2,i):

        if i%j==0:

            a=a+1

            break

            # Added a break here. The moment you encounter a number which divides i, you know # that  the number is obviously composite. So, there is no need to check for further values for j.                  

            # Moreover, rather than i, you can set the upper limit as int(math.sqrt(i)) + 1 because      # once you have checked till the square root of a number, and not found any factors, the           # number is prime.

    if a==0:

        s=s+1

    y.append(s)

    Y.append(i/arr.log(i))

Also, it'll be better to have the initial value if s as 1 rather than 0, because we need to find the number of primes less than or equal to the given integer.

In reply to Ayushman Srivastava .

Re: Number of primes less than or equal to a given number, for a range of values

by Gariman Singh -

I had figured out the break portion but did not put it as I thought that many students might not know about it and it may confuse them.

But I liked setting the upper limit to square root of the number and would like to know its proof.I was thinking about setting the upper limit to half the number as after that only the number itself would be its factor.

The thing that s should be initially 1 is wrong. Read my program carefully and you will understand that it checks the current value of i for primality and then changes the value of s accordingly. Therefore it takes into account the primes equal to the integer.

I would encourage others to improve my code without using break.

In reply to Gariman Singh

Re: Number of primes less than or equal to a given number, for a range of values

by Suroj Dey -
"I liked setting the upper limit to square root of the number and would like to know its proof" 

 The proof of the above is actually an immediate consequence of Fundamental theorem in Number theory.

Let, N be any number

N= \sqrt[]{N} \sqrt[]{N}

N= a*b, i.e two factors-(prime factors)

Now a*b= \sqrt[]{N} \sqrt[]{N} , which implies, that if one of the factors is greater than root of N, then the other must be smaller, so at least one factor must exist which is smaller than root of N. 

However, if both the factors are greater, then the a*b becomes more than N, which is not possible, so the Number can't be factorized and thus is a prime number.

So, running a loop till root N and checking for factors less than root N, acts as a test for Prime Numbers.

Having said that, this isn't the most effective prime number check algorithm.

Seive of Erathosthenes , Fermat primality test, Miller-Rabin test are far more effective, with Seive of Erathostenes being the most elegant  algorithm.
In reply to Gariman Singh

Re: Number of primes less than or equal to a given number, for a range of values

by Dr. Amit Kulshrestha -

Thanks for initiating great discussion Ayushman, and Gariman too, for carrying it forward.

As Professor Paranjape points out, to generate a list of primes, one need not check each number one by one for primality! I am writing a Python code to execute this idea.

import matplotlib.pyplot as pl
def KnockMultiplesOf(p, L):
    for n in L:
        if (n%p == 0) and (n != p):
            L.remove(n)
    return L

primesupto = 10000
L = range(2, primesupto+1)
i = 0
p = 2
while p < 100:
    KnockMultiplesOf(p, L)
    i = i + 1
    p = L[i]

Pi = []
CurrentPi = len(L)
for n in range(primesupto-1, 0, -1):
    Pi.insert(0, CurrentPi)        
    if n < L[CurrentPi-1]:
        L.pop()
        CurrentPi = CurrentPi - 1
Pi.insert(0,0)
Pi.insert(0,0)
pl.plot(Pi)
pl.show()

What is happening here? Also, can someone verify if it is indeed efficient?


Keep Pythoning!


In reply to Ayushman Srivastava .

Re: Number of primes less than or equal to a given number, for a range of values

by Kapil Paranjape -

This is a good discussion, ... however ...

There are two points that need to worked into the program.

  1. We need to build the list of primes in increasing order. The primes that are already known should be used in this process. Most of the programs I see here do not do this! You must use the Sieve of Eratosthenes.
  2. As mentioned in the above post, the function is a "step function" with steps at the prime numbers. To plot such a function (especially when the number of steps is large) one only needs to do something likematplotlib.plot.plot(steps,range(1,len(steps)+1)), where steps is the list of steps in increasing order. (Note how the list produced range by is the list of values of the step function at the corresponding steps.)
A program that takes these two aspects into account will be more efficient and less complicated!

In reply to Kapil Paranjape

Re: Number of primes less than or equal to a given number, for a range of values

by Aabhas Gulati . -

Sir , me and Mayank Yadav (MS18062) implemented your suggestions and came up with a code which uses the sieve .


THE FORMAT FOR THE CODE . 

n=10000

l=range(3,n,2)

primes=[2]

i=0

while i**2<n:

    q=l[i]

    if q!=0:

        primes.append(q)

        for x in range(0,n/(2*q)):

            l[i+x*(q)]=0

    i+=1

for x in range(1,(n-1)/2):

    if l[x]!=0:

        primes.append(l[x])

del primes[-1]

print len(primes)



This program terminates in 0.003 for n=10000 . 

THANK YOU .