• We are pleased to announce that the winner of our Feedback Prize Draw for the Winter 2024-25 session and winning £150 of gift vouchers is Zhao Liang Tay. Congratulations to Zhao Liang. If you fancy winning £150 worth of gift vouchers (from a major UK store) for the Summer 2025 exam sitting for just a few minutes of your time throughout the session, please see our website at https://www.acted.co.uk/further-info.html?pat=feedback#feedback-prize for more information on how you can make sure your name is included in the draw at the end of the session.
  • Please be advised that the SP1, SP5 and SP7 X1 deadline is the 14th July and not the 17th June as first stated. Please accept out apologies for any confusion caused.

Excel Challenge #8

S

Steve Hales

ActEd Tutor
Staff member
Got Excel skills? Let's see.

Hoping that this one is a little more doable :)

Here are the usual rules.
  • Create a single Excel formula to solve the stated problem.
  • The shortest formula wins (when calculating the length of the formula there's no need to include the leading "=", or the curly braces that Excel uses to represent array formulae).
  • The formula's number format can be set to whatever you want.
  • Conditional formatting is not allowed.
Problem #8

Assume that cell A1 contains a positive integer value. Create a single formula to determine whether or not the value in A1 is prime. The output should be either TRUE or FALSE. For example

A1
2 --> TRUE
16 --> FALSE
17 --> TRUE
120 --> FALSE
1024 --> FALSE
472882049 --> TRUE
982451652 --> FALSE
982451653 --> TRUE
982451654 --> FALSE
 
=SUM(((A1/ROW(A:A))=INT(A1/ROW(A:A)))+0)=2
enter as an array function

"A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself."
i.e. only 2 divisors.
Gives FALSE for 1
only works up to no. of rows in excel so fails for the larger examples.
 
Last edited by a moderator:
version 2.
other than itself, the next largest divisor is <= SQRT(A1) so

=AND(A1>1,SUM(((A1/ROW(OFFSET(A1,0,0,SQRT(A1))))=INT(A1/ROW(OFFSET(A1,0,0,SQRT(A1)))))+0)=1)

again, as an array function.
 
Code: 
=SUM(1*(MOD(A1,ROW(OFFSET(A1,,,SUM(A1))))=0))=2
46:cool:

Reference: Prime number has two 0 remainders while dividing the number by all numbers in between [1,the number]...(we know :D )
while composite number has more or less.
 
Hemant Rupani said:
A1<(2^20+1)^0.5
Click to expand...

I think that should be "^2" rather than "^0.5" (and I'm not sure about the "+1" either :) ). Either way we could check for values A1 < 1,099,511,627,776. Now this is about 10^12, and Excel only displays number with up to 15 digits of precision - after that it will use trailing zeroes in which case it won't think there are more primes :D . It might possible to use the Sieve of Eratosthenes to boost the search from 10^12 to 10^15.

This leads to an interesting question; what is the largest prime number Excel can display?
 
Steve Hales said:
I think that should be "^2" rather than "^0.5" (and I'm not sure about the "+1" either :) ). Either way we could check for values A1 < 1,099,511,627,776. Now this is about 10^12, and Excel only displays number with up to 15 digits of precision - after that it will use trailing zeroes in which case it won't think there are more primes :D . It might possible to use the Sieve of Eratosthenes to boost the search from 10^12 to 10^15.

This leads to an interesting question; what is the largest prime number Excel can display?
Click to expand...

ohhh yes! that's ^2, I edit it.
Actually Excel 2007 and later has 2^20 Rows, so if we use SQRT, we check upto 2^20 length(not 2^20+1).... that's why I thought A1 should be less then (2^20+1)^2, I checked too.;)
I would have submitted my formula with SQRT, but MOD function has limitation as ('divisor' * 2^27) should be more than the 'number'...

But I can't get how Sieve of Eratosthenes boosts the search from 10^12 to 10^15?

now, for the next Q, do you challenging us for formula for that or just a number:107928278317(I just searched list of 12-digit prime number on the internet :p )
 
Last edited:
Hemant Rupani said:
But I can't get how Sieve of Eratosthenes boosts the search from 10^12 to 10^15?
Click to expand...

You're current submission looks like

Code: 
=SUM(1*(MOD(A1,ROW(OFFSET(A1,,,SUM(A1))))=0))=2

By changing the SUM to SQRT would give a substantial increase (assuming that the "=2" goes to "=1" as well). This leave

Code: 
=SUM(1*(MOD(A1,ROW(OFFSET(A1,,,SQRT(A1))))=0))=1

This checks every number between 1 and SQRT(A1) for a potential factor, but we know that once "2" has been checked then all other even numbers can be ignored. Something like this might work;

Code: 
=SUM(1*(MOD(A1,1+2*ROW(OFFSET(A1,,,SQRT(A1)/2)))=0))=1

This checks odd numbers between 3 and SQRT(A1), but the OFFSET function can now handle twice as many rows. Would this double the searching power? If so, then a similar process might be implemented for multiples of 3, 5, 7 and 11. I think that this would boost the search sufficiently well to reach 15 digits.
 
Here are a couple of implementations of the Sieve of Eratosthenes:

Based on primes 2 and 3
Code: 
=PRODUCT(--({2,3}*INT(A1/({2,3}))<>A1))*PRODUCT(--(MOD((A1/({1,5}+2*3*ROW(OFFSET(A$1,,,SQRT(A1)/2/3)))),1)<>0))=1

Based on primes 2, 3 and 5
Code: 
=PRODUCT(--({2,3,5}*INT(A1/({2,3,5}))<>A1))*PRODUCT(--(MOD((A1/({1,7,11,13,17,19,23,29}+2*3*5*ROW(OFFSET(A$1,,,SQRT(A1)/2/3/5)))),1)<>0))=1

By extending this to include primes 2, 3, 5, 7 and 11 then Excel can verify that 999,999,999,999,989 is prime, and therefore the largest that it can represent. The formula is pretty long (1,650 characters) because it needs to include the list of primes less that 2*3*5*7*11=2,310.

Watch out for the 2-dimensional array formula here - I don't think it's been used in the Challenges before and could be useful in the future :)
 
You must log in or register to reply here.
Back
Top