C# - Check Primality In Number Inputs

AceInfinity · Mar 31, 2012

Not much programming talk here, but here's the first thread on some C# code I came up with. :thumbsup2:

I'll post the usage as well so you can try it out. To see, you can change around the variable of x which is just a type Int32 (32 bit signed integer).

Code:

private void button1_Click(object sender, EventArgs e)
{
	int x = 21;
	MessageBox.Show(x + (IsPrime(x) ? " is a prime" : " is not a prime"));
}

private bool IsPrime(int input)
{
	if (input == 2)
	{
		return true; 
	} else if (input == 1 || input % 2 == 0) {
		return false; 
	}

	for (int n = 3; n < input / 2; n += 2)
	{
		if (input % n == 0 && n != input) { return false; }
	}
	return true;
}

Nice efficient way of checking for primes :) I think I posted a VB.net version of this as well. But basically the way it works is it does a few firsthand checks; the only prime number divisible by 2 is 2. 0 and 1 are special numbers, NOT prime numbers.

If we know a prime number other than 2 cannot be divisible evenly by 2 then we can skip all even numbers from 3 and up. So in our loop, we can utilize n to check each odd number from 3 forward by adding 2 each time.

Lastly, we only need to go just before the halfway point, as any further and we'll basically be checking the multiples in reverse.

Example:
3 * 7

If we know 21 is divisible by 3, which is 7, then we don't need to continue our loop to 7 since we know it's divisible by a factor of 3... Bad example, as 7 is not the halfway point for 21, but you can see the strategy in not having to go anywhere past the halfway point as we'll start running into the opposite multiples by that point undoubtedly.

niemiro · Mar 31, 2012

Lastly, we only need to go just before the halfway point, as any further and we'll basically be checking the multiples in reverse.

I need to go out like right now, and so I am probably not putting enough thought into this, but wouldn't the maximum we need to go up to be the square root of x, rather than half of x? I am probably wrong

Nice code though!

AceInfinity · Mar 31, 2012

Hadn't tested in full, but crunching a few numbers, it seems valid. No guarantee though, but I never thought about square root before, never knew how prime numbers could be validated quite this much or put enough thought into it to come out with that :)

If this is true, that speeds things up quite a bit more. I thought I had you with 81, because I was thinking 9x9 when I seen 6.~... After the square root calculation. Then after a few number checks I forgot about 3x27 lol. :lol:

Laxer · Mar 31, 2012

Something the might help you out....

By definition an integer

if not prime is guaranteed to have a prime factor between 2 and sqrt

If there is not a prime factor then the integer is prime....

an example:

Is 9 prime?

N=9

Using the theorem above we get the 9 should have a prime factor between 2 and sqrt(3)

So 2<X<3

where x is only prime integers...

so therefore 9 must be divisible by 2 or 3 or else it is prime...

Sure enough, 9 is divisible by 3 so it is not prime...

Little better example... lets try 27.

n=27

by definition 2<X<sqrt(27) -> 2<x<5

This give us possible x values of: 2,3,5

As 27 is not divisible by any x value it must be prime....

Does that make sense? I can't remember the name of the theorem but I can find a page if that is confusing.

AceInfinity · Mar 31, 2012

That does help as it confirms the square root part, however I am trying to solve for primes, so there's not really an efficient way that I can use that part to my advantage, as checking for primes to use in my check would require iterating through each number anyways, however i've narrowed it down to odd numbers, and that's fair enough for having a fast function as this will already scan 10000001 basically in a fraction of a second. Unless I move over to Int64 or something even larger, it's now just a limitation of that data type.

Edit: There we go 10000000000000000001 in a split second :)

Code:

private void button1_Click(object sender, EventArgs e)
{
	UInt64 x = 10000000000000000001;
	MessageBox.Show(x + (IsPrime(x) ? " is a prime" : " is not a prime"));
}

private bool IsPrime(UInt64 input)
{
	if (input == 2)
	{
		return true;
	}
	else if (input == 1 || input % 2 == 0)
	{
		return false;
	}

	for (UInt64 n = 3; n < Math.Sqrt(input); n += 2)
	{
		if (input % n == 0 && n != input) { return false; }
	}
	return true;
}

Laxer · Mar 31, 2012

I would just create an array of known primes...

x={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523}

Then get the input

Take the sqrt and round down.... then mod N with all the values in the array up to that point...

just with the list I have here we can find if an integer is prime up to the number: 292,680

I was just thinking this might be more efficient then your approach.

AceInfinity · Mar 31, 2012

That's only justifiable up to a certain number though, as for once you're outside of the bounds of this array, then you'll have to do a manual check, and for the speed of the current function i'm not sure if it's worthwhile lol. Although it would be easy to do this, just need to check for the square root of the input being larger than 523 in the case of the array you provided above. :)

In the case of the array above, it would work for an input of <= 273529 I believe, before having to do a manual check.

I created a program before to check for prime numbers, and I can get up to the first prime numbers from 2-10000 in a few seconds lol, so the array itself wouldn't be hard to make with the tools I currently have. Just depends on how far you're willing to go, and a larger array will require more memory consequently.

It IS an idea though!

-Save a fraction of a second for evaluating smaller numbers or conserve the memory for the actual process? That's the balance in this decision to be made :)

Edit: An array like that would take 792bytes of memory extra though assuming these were 64 bit integers. Otherwise default 32 bits, and it would be half that. The difference on both sides of the coin here is fairly small though from a perspective that i'm not sure which would be better. Probably writing less code though is the way I would go... It's up to the programmer's view on that one. :grin1:

Laxer · Mar 31, 2012

What it comes down to...

More memory required or more processing required...

The reason for my number -> 292,680

is because it is one less then the next prime squared(541)

I generated my list very quickly doing a google search :grin1:

I know of a few ways to check primality if you are curious :)

AceInfinity · Mar 31, 2012

I've already got quite a big list here if you would like a big list of them lol: http://tech.reboot.pro/showthread.php?tid=2020

My function there loops through each number in a similar way to add prime numbers to an array which can be exported to a text file. Here's what it came out with:

:lol: Now you have all the prime's from 0-100000

Code:

Laxer · Mar 31, 2012

With that list you could check for primality for integers up to: 10,000,600,008!

I would be interested to compare computing times for integers that big using lists vs your script.

AceInfinity · Apr 1, 2012

That wouldn't be too difficult actually, you can use a stopwatch to trigger when the process starts and record it down to a matter of milliseconds. It will vary though, it's not going to be right on the dot every time for each method.

Laxer · Apr 1, 2012

I have seen timers in some of your other programs....

I was just curious :grin1:

AceInfinity · Apr 1, 2012

Code:

private void button1_Click(object sender, EventArgs e)
{
	UInt64 x = 18446744073709551615;
	System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
	sw.Start();
	Console.WriteLine(x + (IsPrime(x) ? " is a prime" : " is not a prime"));
	sw.Stop();
	MessageBox.Show(sw.ElapsedMilliseconds + "ms");
}

Result: 0ms

lol I don't even think it's worth trying to look for the most optimized code in comparison here, for such a small difference that it would have to make to beat this, I don't think it's justifiable doing a test. This is not actually 0ms, but a fraction of a millisecond by less than half of a single millisecond. For scanning 18446744073709551615!!! (Largest an unsigned 64 bit integer can go)

What is that? lol eighteen quintillion something.

(My number converter, converts that to words: eighteen quintillion four hundred forty six quadrillion seven hundred forty four trillion seventy three billion seven hundred nine million five hundred fifty one thousand six hundred fifteen)

Laxer · Apr 1, 2012

Now say that 5 times fast :rofl12:

There was no real reason I was just curious.

Thanks Ace :grin1:

niemiro · Apr 2, 2012

AceInfinity said:
Code:

private void button1_Click(object sender, EventArgs e) { UInt64 x = 18446744073709551615; System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch(); sw.Start(); Console.WriteLine(x + (IsPrime(x) ? " is a prime" : " is not a prime")); sw.Stop(); MessageBox.Show(sw.ElapsedMilliseconds + "ms"); }

Result: 0ms

lol I don't even think it's worth trying to look for the most optimized code in comparison here, for such a small difference that it would have to make to beat this, I don't think it's justifiable doing a test. This is not actually 0ms, but a fraction of a millisecond by less than half of a single millisecond. For scanning 18446744073709551615!!! (Largest an unsigned 64 bit integer can go)

What is that? lol eighteen quintillion something.

(My number converter, converts that to words: eighteen quintillion four hundred forty six quadrillion seven hundred forty four trillion seventy three billion seven hundred nine million five hundred fifty one thousand six hundred fifteen)

I wonder how long it would take to calculate every number up to that number...

The worst case scenario is terrifying! 18446744073709551615 * 0.5 = 922337203685477.5 (milliseconds)
922337203685477.5 / 1000 = 922337203685.4775 (seconds)
922337203685.4775 / 60 = 15372286728.09129 (minutes)
15372286728.09129 / 60 = 256204778.8015215 (hours)
256204778.8015215 / 24 = 10675199.11673006 (days)
10675199.11673006 / 365.25 = 29227.10230453132 (years)
29227.10230453132 / 1000 = 29.22710230453132 (millennia)

I challenge you to optimize that down to within your own lifetime!

BTW, are the calculations correct? I might have slipped something somewhere.

Laxer · Apr 2, 2012

You could just create an array up to that point then find and subtract all the primes to get the composites....

You can calculate primes pretty quickly... http://cr.yp.to/primegen.html

AceInfinity · Apr 2, 2012

@niemiro - There's a bit of a miscalc there but not that it matters being that this is still a huge number based on that logic lol

= 292271.0230453131989599969579435.... years
= 292.2710230453131989599969579435.... millennia

For each number, in calculating all primes up to that number though (18446744073709551615)... You'd need to iterate through each number and check for factors from 1 eventually up to the square root of that number (18446744073709551615), which is 4294967296.

So if you look at that, for each increasing value that you're checking as prime, you would need to (for each of those number being checked for primality) check from 1 and eventually up to 4294967296 times PER number!! 4294967296 could be shortened however to approx. HALF, by only having to check each ODD number to see if it's a factor of the main inputted number in question. Which is ~2147483647 for each loop/iteration (the max value of a 32 bit signed integer)

AceInfinity · Apr 2, 2012

If I was to do that though i'd probably do something similar to this:

Code:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;

namespace CSharp_Tester
{
	public partial class Form1 : Form
	{
		public Form1()
		{
			InitializeComponent();
		}

		private void button1_Click(object sender, EventArgs e)
		{
			//18446744073709551615
			new System.Threading.Thread(startProc).Start();
		}

		private void startProc()
		{
			UInt64 num = 18446744073709551615;
			UInt16 vBuffer = 50, dBuffer = 1000, exp_count = 1;
			StringBuilder sb = new StringBuilder();

			for (UInt64 i = 0; i < num; i++)
			{
				if (sb.Length < vBuffer)
				{
					sb.AppendLine(IsPrime(i) ? i + " = Prime" : i + " != Prime");
				} 
				else
				{
					textBox1.Invoke((MethodInvoker)delegate { textBox1.Text += sb.ToString(); });
					sb.Clear();
				}

				if (textBox1.Lines.Length >= dBuffer)
				{
					using (System.IO.StreamWriter sw = new System.IO.StreamWriter(Application.StartupPath + "\\PrimesExport" + exp_count.ToString() + ".txt"))
					{
						sw.Write(textBox1.Text);
					}
					textBox1.Invoke((MethodInvoker)delegate { textBox1.Clear(); });
					exp_count++;
				}
			}
		}

		private bool IsPrime(UInt64 input)
		{
			if (input == 2)
			{
				return true;
			}
			else if (input == 1 || input % 2 == 0)
			{
				return false;
			}

			for (UInt64 n = 3; n < Math.Sqrt(input); n += 2)
			{
				if (input % n == 0 && n != input) { return false; }
			}
			return true;
		}


	}
}

For counting up that high especially, you'd have to bite it off in chunks, and clear the output buffer every once in a while too, to make sure that you're not holding a large amount of data.

I've been running this for about 3 minutes so far, and i've scanned through ~67000 numbers and exported each checked value into ~50 text files so far doing this.

Edit: It still wraps my code inside the code box, horizontal scrollbar is ommitted when long lines are present it seems.

You would hardly get far enough in a lifetime to do this though unless you had some kind of quantum/super computer. Otherwise, it'll cost ya at the price of more RAM usage, and I can scan multiple ranges of up to the final value at the same time and export to files at the same time?

Last thing to note: This process WILL inevitably slow down as the looped "value" increases as you're checking more numbers throughout that single process within the loop to validate that single number as prime or not prime.

Edit: Just at 300 000 now... Too slow to reach even a million quick enough. Perhaps to speed this up a bit, don't even put the even numbers into the function at all? Check for the actual input, and if even automatically put "False" into the output, go to the next number in the sequence and from there count every second number and assume that each number in between (being all the even number) are not prime by just writing the text into the textbox without piping it to the function?

So who wants ~300 text files (~15kb each) with an output of the numbers from 0-300 000 so far being defined as prime or not? :lol:

Last Edit: I'm going to stop the program now.

niemiro · Apr 2, 2012

I remember writing a prime factors calculator for numbers up to a million which had to run in less than a second at my last British Informatics Olympiad Round 1...

I didn't use a very efficient algorithm. I pretty much brute forced it up to the square root. It worked fast enough (in less than 1 second) and it was quick, which was a bonus, because I had three programs to write in three hours, and the other two were much, much harder!

niemiro · Apr 2, 2012

On a slightly off topic note, a fun challenge someone once set me was to calculate nCr, when

nCr = (n!) / (r!*(n-r)!)

for

0 <= n <= 100

using only 32bit integers.

C# - Check Primality In Number Inputs

Emeritus, Contributor

Senior Administrator, Windows Update Expert

Emeritus, Contributor

Administrator

Emeritus, Contributor

Administrator

Emeritus, Contributor

Administrator

Emeritus, Contributor

Administrator

Emeritus, Contributor

Administrator

Emeritus, Contributor

Administrator

Senior Administrator, Windows Update Expert

Administrator

Emeritus, Contributor

Emeritus, Contributor

Senior Administrator, Windows Update Expert

Senior Administrator, Windows Update Expert