A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Divide a number by each number between 2 and square root of the number. If the number has no factors less than its square root, then n is prime.
Let's take a number 53
- Calculate square root of 53 i.e. 7.28
- Round 7.28 up i.e. 8
- Divide 53 by each number between 2 and 8 (2,3,4,5,6,7,8)
- You'll see there is always a remainder when 53 is divided by each number 2 and 8
- Result : Prime
Excel Formula to Check Prime Number
Suppose a number is entered in cell B2. Paste the formula below in cell C2 to check if it is prime.
=IF(INT(B2)=2,"Prime",IF(AND(MOD(INT(B2),ROW(OFFSET($A$2,,,ROUNDUP(SQRT(INT(B2)),0)-1)))<>0),"Prime","Not Prime"))
Make sure to hit CTRL + SHIFT + ENTER to confirm this formula as an array formula. If done correctly, Excel will automatically place curly braces {...} around the formula.
Note : If you find the formula is not returning the correct prime number, it is likely that you pressed just ENTER instead of CTRL + SHIFT + ENTER to apply the formula.
Download the workbook- This section of formula
ROW(OFFSET($A$2,,,ROUNDUP(SQRT(INT(B2)),0)-1)creates a list of numbers from 2 to the square root of the number. - Each number in the list is divided into the number in question using the MOD function.
- If any of these divisions result in zero remainder, it means the number is not prime.
- The formula checks if all these divisions result in non-zero remainders using the AND function. If yes, the number is prime.
Deepanshu founded ListenData with a simple objective - Make analytics easy to understand and follow. He has over 10 years of experience in data science. During his tenure, he worked with global clients in various domains like Banking, Insurance, Private Equity, Telecom and HR.
It is working fine for 9. Download the workbook (link provided in the article)
ReplyDeleteYour formula references A2, but doesn't say what I should be putting there. It's great that your formula works for your specific workbook, but if it can't be easily copied into another, then what is the point of publishing it.
ReplyDeleteAnonymous, it is very easily copied into any workbook, and it works exactly as advertised. The A2 reference makes no difference - a little investigation would have shown you that. And on that note, even if the formula wasn't directly translatable, would it really hurt to have to -gasp!- do a little of your own homework? There's a lot to learn from this post - that would be "the point" of publishing it.
ReplyDeleteDoesn't seem to be 100% accurate, for example, For the input I entered 111,111,111. It said it was prime, although it can be divided by 9 and 3 at least. Any idea what may cause this kind of behavior? I don't really understand how the function works, so I can't diagnose the problem myself.
ReplyDeleteIt says 'Not Prime' for 111,111,111. You can save your workbook to any cloud drive and share link with me to debug.
DeleteFrom Malinborn asnswer: The reason it is not working for some people is, I think, they are skipping the Ctrl+Shift+Enter aspect to make it an array formula.
DeleteClever!! I never would have thought of using an array formula iterating along a virtual array to create a "for loop" inside an excel formula! I'm definitely going to have to remember that technique in the future!
ReplyDeleteThough, as evidenced by the comments, that technique is extremely advanced (and thus confusing) for most people. Perhaps a link to a post with an explanation of the technique would help.
Careful using this with numbers 81 and larger...
ReplyDeleteIt works fine for me. Make sure to press CTRL + SHIFT + ENTER after entering the formula but BEFORE clicking away. You will know that you entered it correctly if selecting the cell shows
Delete{=IF(B4=2,"Prime",IF(AND(MOD(B4,ROW(OFFSET($A$2,,,ROUNDUP(SQRT(B4),0)-1)))<>0),"Prime","Not Prime"))}
note the {} brackets.
Also note that entering the brackets manually does NOT work; you have to press CTRL + SHIFT + ENTER to get the brackets.
Shows 6 as a prime, not correct
ReplyDeleteThe formula works, the most common mistake is not making it an array formula by pressing Ctrl+Shift+Enter. If you don't make it an array formula it will return false positives (like 9, 81, and 1681).
DeleteThank you that is genius, works fine for me, shows 6 and 9 as prime.
ReplyDelete74 Prime
ReplyDelete75 Not Prime
76 Not Prime
77 Not Prime
78 Not Prime
79 Prime
80 Not Prime
81 Not Prime
82 Prime
83 Prime
84 Not Prime
85 Not Prime
86 Prime
87 Not Prime
88 Not Prime
89 Prime
90 Not Prime
91 Not Prime
92 Not Prime
93 Not Prime
94 Prime
try 1681 it says its prim but 41^2 = 1681
ReplyDeleteThanks, this formula works completely fine with me. I would really appreciate, if you could give a little bit explanation for this particular part - IF(AND(MOD(B4,ROW(OFFSET($A$2,,,ROUNDUP(SQRT(B4),0)-1)))<>0),"Prime","Not Prime"))
ReplyDeleteThe formula creates a virtual array from 2 (which is why A2 is used in the formula) to the square root of the number (because there are no possible multiples larger than the square root of a given number). That is the "OFFSET($A$2,,,ROUNDUP(SQRT(B4),0)-1)" section.
DeleteNext, every function the array is passed to acts on every entry in that array until it is summarized by the AND function.
So first the array is passed to the ROW function which places the "row number" in each array entry. The array of numbers is then passed to the MOD function as the divisor. The formula then returns the remainder when the number in question is divided by the number in that entry in the array. That is the "MOD(B4,...)" section. It then tests each entry to see if that result is equal to 0, if an entry in the array is 0, then it returns FALSE. The array is now a list of TRUE and FALSE values that are then summarized with the AND function. AND takes the array of Boolean values and returns a single Boolean value.
So, if the number is not prime then there is a divisor somewhere in the array of integers and the MOD function returns 0, the logical comparator "<>0" then returns FALSE which then makes AND false, causing the IF function to return "Not Prime".
Because the formula uses an array, you MUST tell Excel to process it as an Array Formula by entering it with Ctrl+Shift+Enter. Otherwise, if you don't make it an array formula it will return false positives (like 9, 81, 1681, and now the latest entry, 21).
This Formula is not correct because for 21 it also says it is a prime number but 21 can be divided by 3 and so this formula is not perfect i want a perfect formula brother
ReplyDeleteit says not prime for 1681 in my case
ReplyDeleteThe correct formula should be like this:
ReplyDelete=IF($C$4=2,"Prime",IF(AND(MOD(C4,ROW(OFFSET($A$2,,,ROUNDUP(SQRT($C$4),0)-1)))<>0,MOD($C$4,SQRT($C$4))<>0),"Prime","Not Prime"))
Why test for the square root again? It's already included in the virtual array.
ReplyDeleteWhen evaluated as an array formula, the offset function creates an array from 2 to the square root (rounded up, so the square root is always included). Your function just adds a test for the un-rounded square root. But, the only time an un-rounded square root would make a difference (ie, be a divisor) is if it happens to be an integer, which is already included in the array as the round functions don't change an integer.
As long as you make it an array formula with Ctrl+Shift+Enter, this modification won't change anything.
Very clever. the AND function with a single Logical parameter confused me until I saw the that the array was being summarized via the CSE capability. Wow a real brain twister.
ReplyDeleteThe reason it is not working for some people is, I think, they are skipping the Ctrl Shift Enter aspect to make it an array formula.
ReplyDeleteThe formula provided by Deepanshu is a good idea, very well engineered - it works AS LONG AS the "integer" to be tested is (actually) an integer - without the inaccuracies of Excel, the IEEE-754 standard, or an old Intel processor that also had this type of problem.
ReplyDeleteExcel uses a modified version of the IEEE-754 standard, where some items do not fully adhere to this standard: Excel disregards, without rounding, digits beyond the 15th position, and as if that were not enough, results from floating-point arithmetic are presented in a cell in a "user-friendly manner" (without precision errors) differently how it is stored in memory in binary form according to IEEE-754. More, decimals of (mainly) multiples of 3 (1/3, 1/6, etc.) generate considerable errors in any binary arithmetic, regardless of the chosen standard.
Let's take the example of Muhammad Hassan (April 27, 2020):
1. If we type "21" in the testing cell: [ 21] [Not Prime ] - it works;
2. If we get "21" from a floating-point arithmetic formula such as:
= (2^6 - 1) / (27^(1/3)) [Prime ] - Deepanshu's formula may fail in some (if not all) versions of Excel.
A formula like this can result in Real values from 20.9999999999993 to 21.0000000000003 - even if the test cell shows "21". In the 2019 and 365 versions of Excel, we can verify it in the formula field ( fx ) when we highlight the MOD(...) function up to its closing parentheses - the results of the function's dynamic array will appear in a white band with Real numbers (as remainders of MOD divisions) making the prime number formula fail.
Solutions:
1. You can continue using Deepanshu's original formula as long as in any arithmetic operation, the result has its decimal part truncated with INT(...) or rounded with ROUND(...; 0).
Examples:
= INT( (2^6 - 1) / (27^(1/3)) ) or
= ROUND( (2^6 - 1) / (27^(1/3)); 0 )
The result will be "21" without any inaccuracy and then [Not Prime ];
2. You can use an alternative formula:
2A. That truncates the decimal part of the tested number:
= IF( AND( MOD( INT(B4); ROW( OFFSET($A$2; ; ; ROUNDUP( SQRT(B4); 0 ) - 1) ) ) <> 0 ); "Prime"; "Not Prime" )
2B. And also truncate the Square Root Limit to improve performance in software known for memory-hogging, speed limitations, and inaccuracies - this is what I use in my research in Excel 365:
= IF( AND( MOD( INT(B4); ROW( OFFSET($A$2; ; ; INT( SQRT(B4) )) ) ) <> 0 ); "Prime"; "Not Prime" )
Remember that these formulas confirm numbers such as 23.01, 23.5, or 23.9999 as [Prime ], number "23". In cases of dealing with INTEGER numbers only under primality testing, such as mine, this formula is satisfactory: precise and fast. The primality test for "2" has been removed to increase performance - just as "1" causes the #REF reference error in Deepanshu's original formula, "2" will do the same in these alternative formulas - but I think we all know that "2" is prime - optionally the IF can be added to the "2" test involving any of the formulas above - see below;
3. Primality test of "2"... and "1":
3A. Is "2" prime?
= IF( B4 = 2; "Prime"; [one of the formulas above HERE] )
3B. Is "1" prime? YES, some Mathematicians believe so. Although it cannot be used in the Eratosthenes Sieve nor in the Gaussian density formula, "1" fulfills the most basic requirements of primality in a self-sufficient way. I humbly consider myself in this group of believers - if you also consider yourself the same, then:
= IF( OR(B4 = 1; B4 = 2); "Prime"; [one of the formulas above HERE] )
Thanks for the detailed explanation. I never thought users would intentionally or unintentionally check prime numbers for decimal numbers. Thanks for bringing it to my attention. Cheers!
DeleteSome notes:
ReplyDeleteN1. The formulas presented here are in 'international locale format' - most notably the semi-colon separator (;) because it better serves the understanding of readers who use international versions of Excel. If you use an English version of Excel (or an English "regional settings"), please replace semi-colon (;) per comma (,);
N2. I consider Excel formulas a Programming Language, and therefore, they shall be treated in a structured way to make them more readable and easier to understand even because the formulas are not mine alone - hence the spaces that do not affect the formula. IF indentation, Consolas (monospace fixed-width font) in the formula field (fx), when very large, break them with Alt+Enter, etc. If you consider this unnecessary, feel free to delete the spaces in the proposed formulas;
N3. These formulas (original and alternative) are suitable for numbers in INTEGER format. Avoid exceeding the Integer limit for your version of Excel - in versions 2019 or 365, the limit is 15 digits "9" (999 999 999 999 999) - in some old versions, it was a power of 2 minus 1;
N4. In versions 2019 or 365, the dynamic array is automatic - no need for {CSE} (Ctrl+Shift+Enter) for both the original formula and the alternatives. If you intend to distribute your spreadsheet to readers with older versions, use {CSE} for compatibility. In any case, it is recommended to keep the MOD(...) calculation column, in this case, the A$ column free to avoid #VALUE or #SPILL errors;
N5. The MOD function gives, as a result, the remainder of the division, not the quotient. As far as I remember, this function was always... complicated - I can remember to avoid its use by working around it with formulas such as "A1/B1 - INT(A1/B1) <> 0". The XLS-type versions had a MOD limited to 255 or 65535 in the divider; in other XLSX-type versions, there were precision errors if the number was greater than 256M and divisor 2. Only in recent updates to version 365 did the MOD function become more flexible. Please check the MOD function status of your Excel version on the Microsoft Learn Center;
N6. Hint: Dynamic arrays are huge resource hogs. If there is a large amount of numbers to test - list the numbers horizontally using the maximum number of cells in the row (recommended). And the primality test formula in the next row. This is because Excel has Z-scanning. Otherwise, by listing the numbers in a single column, Excel checks each cell for values or formulas for all rows up to the last cell in the worksheet, even if they have no content. This procedure is valid for any spreadsheet with lots of data. Always remember to leave the A$ calculation column free: the XLSX-type versions with 1M rows can test integers of up to 12 digits, and the XLS-type versions with 65535 rows can test integers of up to 4G (10 digits). There is not much advantage in changing the ROW function to COLUMN in the provided formulas since the versions have 16K and 255 columns, respectively - these are restricted limits for testing large integers.
Hope this helps. A happy prime number hunt for everyone.