[C++] IsPrime(int x)

Darthfett · Apr 23, 2010

ToolTipError said:
I'm a bit confused. How would I find the square root of the number?

I haven't tested, but basically you swap out y <= x/2 with y <= sqrt(x). If you understand patterns, you would know that if you start comparing non-prime numbers factors from 1 to the number, you will start repeating the factors after you hit sqrt(n).

For example, lets say you have 16. Factors:

sqrt(16) = 4

16 = 1 * 16
16 = 2 * 8
16 = 4 * 4
16 = 8 * 2
16 = 16 * 1

After 4 (or sqrt(n)), you can stop checking the numbers, because if you know that 1, 2, and 4 are factors of 16, you also know that 16/1, 16/2, and 16/4 are also factors of 16. You don't need to do the rest of the numbers.

Fixed, untested code:

ToolTipError said:

Code:

 #include <iostream>
 #include <cstdlib>
 #include <cmath>
  using namespace std;

int isPrime(int x);

 int main ()
{
	int input;
	int count;
	int y;
	cout<<"Please, enter a number: ";
	cin>>input;
	if (isPrime(input)==1) {
		cout<<"Your number is already prime.\n";
		return 0;
	}
	for (count=input; y!=1; count++) {
		if (isPrime(count)==1) {
			cout<<"The next prime number is "<<count<<".\n";
			y=1;
		}
	}
	cin.get();
	return 0;
}

  int isPrime(int x)
{	
	int y;
	for (y=2; y<=sqrt(x); y++)
	{
		if (x%y==0) 
		{
			return 0;
		}
	}
	return 1;
}

Yes, that's true. A further optimization, as suggested by Dave, would be to check for only odd numbers (after checking that n is not 2, of course)

I think you're thinking of the different situation, of finding prime numbers, in that you loop from 3 to n, increasing the iterator by 2. In this case, he's trying to see if a specific number is prime. A simple x % 2 operation will eliminate all even numbers.

Dave312 · Apr 23, 2010

Optimized Code:

Code:

int isPrime(int x)
{	
	int y;
	if (x%2==0)
	{
		return 0;
	}
	for (y=3; y<=sqrt(x); y+=2)
	{
		if (x%y==0) 
		{
			return 0;
		}
	}
	return 1;
}

tom_mai78101 · Apr 23, 2010

If you don't like integers, you can try changing the int to bool, and the 1s and 0s to true and false respectively.

Dave312 · Apr 24, 2010

Darthfett said:
I think you're thinking of the different situation, of finding prime numbers, in that you loop from 3 to n, increasing the iterator by 2. In this case, he's trying to see if a specific number is prime. A simple x % 2 operation will eliminate all even numbers.

It doesn't matter as it applies for both cases. When I brought it up I was only looking at if n was a prime. When you are going through and dividing to determine if n is indeed a prime, you will only need to check all odd numbers and 2 (as all other evens are not primes). So to save time, you should a do check to see if the number is even and then just check odd numbers.

I just realized that the code I had in my last post would report 2 as not being a prime which is obviously incorrect. Below it has been fixed.

Code:

int isPrime(int x)
{	
	int y;
	if (x==2) {
		return 1;
	}
	if (x%2==0)
	{
		return 0;
	}
	for (y=3; y<=sqrt(x); y+=2)
	{
		if (x%y==0) 
		{
			return 0;
		}
	}
	return 1;
}

celerisk · Apr 24, 2010

Dave312 said:
Code:

... for (y=3; y<=sqrt(x); y+=2) ...

You can do faster by calculating the sqrt only once, i.e. outside the loop (though, if you're lucky, your compiler may notice that and do it for you).

Or go one step further by also not testing for any multiples of 3 (except once of course).

Something like this:

Code:

int isPrime(int n)
{
        int a = 5,b = 2, s;

        if (n < 2)
        {
                return 0; /* sanity check */
        }
        if (n == 2 || n == 3)
        {
                return 1; /* handle 2 and 3 as special case */
        }
        if ((n & 1) == 0)
        {
                return 0; /* multiple of 2 */
        }
        if ((n % 3) == 0)
        {
                return 0; /* multiple of 3 */
        }

        for (s = sqrt(n) + 1; a <= s;)
        {
                if ((n % a) == 0)
                {
                        return 0; /* not prime */
                }
                a += b;
                b = 6 - b;
        }
        return 1; /* found one */
}

I know that construct with a and b looks somewhat weird, but it makes sure to only ever get you odd numbers that are not a multiple of 3 (5, 7, 11, 13, 17, ...).
While it won't make much of a difference on small numbers, it helps considerably if they get larger.

Dave312 · Apr 25, 2010

Very nice :thup: I purposely choose not to exclude multiple's of 3 just because I thought the code would get rather messy and complicated.

tooltiperror · May 2, 2010

Since I'm moving onto C# on the recommendation of Vestras, I've remade this in it.

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program
{
    class Program
    {
        static void Main()
        {
            string Input;
            int sqrt;
            int x;
            int y=2;

            Console.Write("[C#] Enter a number: ");
            Input = Console.ReadLine();
            x = Int32.Parse(Input);
            sqrt = (int)Math.Sqrt(9);

            if (x == 0)
            {
                Console.Write("Your number is zero.");
                Console.ReadLine();
                return;
            }
            if (x == 2 || x == 3)
            {
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }
            if (x % 2 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            if (x % 3 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            while (y<=sqrt)
            {
                if (x % y == 0)
                {
                    Console.Write("Your number is composite.");
                    Console.ReadLine();
                    return;
                }
                y++;
            }
            Console.Write("Your number is prime.");
            Console.ReadLine();
        }
    }
}

Just used [ljass]Console.ReadLine()[/ljass] for Microsoft Visual C#.

Darthfett · May 2, 2010

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program
{
    class Program
    {
        static void Main()
        {
            string Input;
            int sqrt;
            int x;
            int y=5;

            Console.Write("[C#] Enter a number: ");
            Input = Console.ReadLine();
            x = Int32.Parse(Input);
            sqrt = (int)Math.Sqrt(9);

            if (x == 0)
            {
                Console.Write("Your number is zero.");
                Console.ReadLine();
                return;
            }
            if (x == 2 || x == 3)
            {
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }
            if (x % 2 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            if (x % 3 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            while (y<=sqrt)
            {
                if (x % y == 0)
                {
                    Console.Write("Your number is composite.");
                    Console.ReadLine();
                    return;
                }
                y+=2;
            }
            Console.Write("Your number is prime.");
            Console.ReadLine();
        }
    }
}

Couple optimizations: y starts at 5, y+=2 instead of y++.

Vestras · May 3, 2010

ToolTipError said:

Since I'm moving onto C# on the recommendation of Vestras, I've remade this in it.

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program
{
    class Program
    {
        static void Main()
        {
            string Input;
            int sqrt;
            int x;
            int y=2;

            Console.Write("[C#] Enter a number: ");
            Input = Console.ReadLine();
            x = Int32.Parse(Input);
            sqrt = (int)Math.Sqrt(9);

            if (x == 0)
            {
                Console.Write("Your number is zero.");
                Console.ReadLine();
                return;
            }
            if (x == 2 || x == 3)
            {
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }
            if (x % 2 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            if (x % 3 == 0)
            {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }
            while (y<=sqrt)
            {
                if (x % y == 0)
                {
                    Console.Write("Your number is composite.");
                    Console.ReadLine();
                    return;
                }
                y++;
            }
            Console.Write("Your number is prime.");
            Console.ReadLine();
        }
    }
}

Just used [ljass]Console.ReadLine()[/ljass] for Microsoft Visual C#.

-->

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program {
    public class Program {
        private static void Main() {
            Console.Write("[C#] Enter a number: ");
            string input = Console.ReadLine();
            int squareroot = (int)Math.Sqrt(9);
            int x = Int32.Parse(input);
            int y = 2;
            if (x == 0) {
                Console.Write("Your number is zero.");
                Console.ReadLine();
                return;
            }

            if (x == 2 || x == 3) {
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }

            if (x % 2 == 0) {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }

            if (x % 3 == 0) {
                Console.Write("Your number is composite.");
                Console.ReadLine();
                return;
            }

            while (y <= squareroot) {
                if (x % y == 0) {
                    Console.Write("Your number is composite.");
                    Console.ReadLine();
                    return;
                }

                y++;
            }

            Console.Write("Your number is prime.");
            Console.ReadLine();
        }
    }
}

Code guidelines are important. Type out everything, and if you think you'll code faster, you're wrong - you have the Visual Studio intellisense to help with that.
But overall, :thup:

celerisk · May 3, 2010

Vestras said:
Code guidelines are important.

It also helps to use code that works.

As in, " (int)Math.Sqrt(9); ":
That's a constant... you probably didn't want that 9 there.

tooltiperror · May 3, 2010

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program
{

    class Code
    {
        bool isPrime(int x){
            int y = 5, sqrt = (int)Math.Sqrt(x);
            if (x == 0){
                return false;
            }
            if (x == 2 || x == 3){
                return true;
            }
            if (x % 2 == 0){
                return false;
            }
            if (x % 3 == 0){
                return false;
            }
            while (y <= sqrt){
                if (x % y == 0){
                    return false;
                }
                y++;
            }
            return true;
        }

        static void Main(){
            int x;
            bool y = true;
            Console.Write("Please enter a number: ");
            x = Console.Read();
            if (y == true){
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }
            Console.Write("Your number is composite.");
            Console.ReadLine();
        }
    }
             
}

Alright, this is my code now. I just converted [ljass]isPrime()[/ljass] to return booleans rather than just print a line. Now, the problem is, in my [ljass]Main()[/ljass] method, I should change [ljass]x = Console.Read();[/ljass] to [ljass]x = isPrime(Console.Read());[/ljass]. But I get an error for that: What do need to do to call methods?

Edit: Top of the page wave.

Vestras · May 3, 2010

ToolTipError said:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program
{

    class Code
    {
        bool isPrime(int x){
            int y = 5, sqrt = (int)Math.Sqrt(x);
            if (x == 0){
                return false;
            }
            if (x == 2 || x == 3){
                return true;
            }
            if (x % 2 == 0){
                return false;
            }
            if (x % 3 == 0){
                return false;
            }
            while (y <= squareroot){
                if (x % y == 0){
                    return false;
                }
                y++;
            }
            return true;
        }

        static void Main(){
            int x;
            bool y = true;
            Console.Write("Please enter a number: ");
            x = Console.Read();
            if (y == true){
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }
            Console.Write("Your number is composite.");
            Console.ReadLine();
        }
    }
             
}

Alright, this is my code now. I just converted [ljass]isPrime()[/ljass] to return booleans rather than just print a line. Now, the problem is, in my [ljass]Main()[/ljass] method, I should change [ljass]x = Console.Read();[/ljass] to [ljass]x = isPrime(Console.Read());[/ljass]. But I get an error for that: What do need to do to call methods?

Edit: Top of the page wave.

As I said, code guidelines are important:

Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Program {
    public class Code {
        bool IsPrime(int x) {
            int y = 5;
            int squareroot = (int)Math.Sqrt(x);
            if (x == 0) return false;
            if (x == 2 || x == 3) return true;
            if (x % 2 == 0) return false;
            if (x % 3 == 0) return false;
            while (y <= sqrt) {
                if (x % y == 0) return false;
                y++;
            }

            return true;
        }

        static void Main() {
            int x;
            bool y = true;
            Console.Write("Please enter a number: ");
            x = Console.Read();
            if (y == true) {
                Console.Write("Your number is prime.");
                Console.ReadLine();
                return;
            }

            Console.Write("Your number is composite.");
            Console.ReadLine();
        }
    }       
}

bool isPrime --> bool IsPrime
C# is not Java.

This is more important that you think, code guidelines can be the reason in whether you get a job or not. Some companies even make rulesets for their employees.

JerseyFoo · May 5, 2010

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 = prime numbers.

You can check if a number is a prime number by dividing by prime numbers and getting a zero remainder.

Code:

        bool IsPrime(int x) {
            int y = 5;
            int sqrt = (int)Math.Sqrt(x);

            if (x <= 0) return false;
            if (x <= 3) return true;

            if (x % 2 == 0 || x % 3 == 0) return false;

            while (y <= sqrt) {
                if (x % y == 0 || x % (y+2) == 0) return false;
                y = y + 6;
            }

            return true;
        }

Lets see...

starts at 5
checks 5
checks (5+2)=7
checks (5+6)=11
checks (11+2)= 13
checks (11+6)= 17
checks (17+2)= 19
checks (17+6)= 23
checks (23+2)= 25 // not needed
checks (23+6)= 29
checks (29+2)= 31
checks (29+6)= 35 // not needed
checks (35+2)= 37
checks (35+6)= 41
checks (41+2)= 43
checks (41+6)= 47
checks (47+2)= 49
...

Seems to work. I've tested it up to 9001.

Code:

isPrime        15.681ms	0.002ms	0ms	0.143ms	
isPrime2       13.743ms	0.002ms	0ms	0.062ms

Slapshot136 · May 5, 2010

JerseyFoo said:
Seems to work. I've tested it up to 9001.

I don't get where the y+2 or y+6 comes from, but it works

Xienoph · May 5, 2010

Slapshot136 said:
I don't see how it works, but it appears to

Because the while loop checks for all primes below sqrt. Ie: the value of all primes below sqrt are either y, or y + 2. This means that for any prime p below sqrt (and >= 5), either p = 5 + 6n or p = 5 + 6n + 2, or: p - 5 = 0 or 2 (mod 6). n is any integers.

Why is this true? Let's check the possible values of p - 5 in mod 6:
p - 5 = 1:
This means that p - 5 = 6n + 1, or p = 6n + 6. Since 6|p, p can't be prime.

p - 5 = 3:
p - 5 = 6n + 3, or p = 6n + 8. Since 2|p, p can't be prime.

p - 5 = 4:
p - 5 = 6n + 4, or p = 6n + 9. Since 3|p, p can't be prime.

p - 5 = 5:
p= 6n + 10. Since 2 | p, p can't be prime.

So, for all other values of p - 5 in mod 6, p are not prime. This means that for any prime number p, either p - 5 = 0 or p - 5 = 2 (mod 6).

Interesting find :thup:.

Slapshot136 · May 5, 2010

Xienoph said:
the value of all primes below sqrt are either y, or y + 2

ah, I didn't know that, now it makes sense

JerseyFoo · May 6, 2010

For clarification, without caching and mad science/outlandish coding, this is probably the fastest way to do a isPrime function.

Code:

		function isPrime4(x){
			var y = x % 6;
			var sqrt;

			if ( x <= 3 ){
				if ( x <= 0 ) return false;
				return true;
			} 
			else if ( y !== 5 && y !== 1 ) return false;
			// else if ( x % 2 == 0 && x % 3 == 0 ) return false;

			sqrt = Math.floor( Math.sqrt(x) );

                        for (y = 5; y <= sqrt; y += 6)
                                if ( x % y == 0 || x % (y+2) == 0 ) return false;	
			
			return true;
		}

Notice I commented out the second else if, this is because it was yielding slower results in the browser. I don't know if this is true in C++.

For up to 400,000. (most without firefox interrupting)

Code:

isPrime       400000	56.14%	1548.572ms	1548.572ms	0.004ms	0ms	0.626ms	
isPrime4      400000	43.86%	1209.872ms	1209.872ms	0.003ms	0ms	0.35ms

[C++] IsPrime(int x)

Aerospace/Cybersecurity Software Engineer

Censored for your safe viewing

The Helper Connoisseur / Ex-MineCraft Host

Censored for your safe viewing

When Zerg floweth, life is good

Censored for your safe viewing

Super Moderator

Aerospace/Cybersecurity Software Engineer

Retired

When Zerg floweth, life is good

Super Moderator

Retired

1/g = g-1

Divide et impera

You can change this now in User CP.

Divide et impera

1/g = g-1

Log in

The Helper Discord

Share this page

Affiliates

Network Sponsors