Saving Time in Programming Contest

Problem Description

At present Minhajur Rahman Khan is in great problem. In 2006 Minhajur Rahman Khan made a website named http://www.amarpata.com for the students of DUET, Gazipur. It has taken more than 6 months to be completed. When the students of DUET, Gazipur knew about the website, they were becoming the member of the website. Day by day member is increasing. He wants to give special offer to the students whose member’s serial number is prime. The capacity of his database is <=10000000. Now he is looking for a programmer who is able to find the solution within 3 seconds.

Input

The input is an integer n, (1 <= n <= 10000000) the total member of http://www.amarpata.com from standard input.

Output

The output will be the number of students counted to be given gifts.

Problem analysis and solution technic

In this section we will discuss about prime number. Prime numbers start from 2 to those numbers which are not divided by the numbers from 2 to less than the numbers. For example the number 7 is prime. Because the number is not divisible by any number from 2 to less than the number 7. On the Other hand the number 8 is not a prime number. It is divisible by two. Now we want to solute the problem by C++.

  #include<iostream.h>

  void main()
  {
   long i,n,count=0;   
   cin>>n;
   for(i=1;i<=n;i++)
	if(is_prime(i))count++;
   cout<<count;
  }


  int is_prime(long k)
       {

	for(i=1;i<k;i++)
	    if(k%i==0)return 0;	
	return 1;

       }

Have you thought that the number should not be check untill the full number. If you check till the middle of the number it will possible to find the prime number.

  #include<iostream.h>

  void main()
  {
   long i,n,count=0;   
   cin>>n;
   for(i=1;i<=n;i++)
	if(is_prime(i))count++;
   cout<<count;
  }


  int is_prime(long k)
       {

	for(i=1;i<k/2;i++)
	    if(k%i==0)return 0;	
	return 1;

       }

You need not run the loop till the half of the number. It is possible if you go till squre root of the number.

  #include<iostream.h>
  #include<math.h>
  void main()
  {
   long i,n,count=0;   
   cin>>n;
   for(i=1;i<=n;i++)
	if(is_prime(i))count++;
   cout<<count;
  }


  int is_prime(long k)
       {

	for(i=1;i<sqrt(k);i++)
	    if(k%i==0)return 0;	
	return 1;

       }

You don’t need to check the even number. So, you can reduce the program.

  #include<iostream.h>
  #include<math.h>
  void main()
  {
   long i,n,count=0;   
   cin>>n;
   for(i=1;i<=n;i+=2)
	if(is_prime(i))count++;
   cout<<count;
  }


  int is_prime(long k)
       {

	for(i=1;i<sqrt(k);i++)
	    if(k%i==0)return 0;	
	return 1;

       }