Advanced Formula Challenge #10: Prime Factorisation 22

The challenge this week is as follows: given a value in A2, where A2 is an integer and 2<=A2<=100, a formula to be entered into B2 such that, if the value in A2 is a prime number, return "Prime"; otherwise, return a string representing the prime factorisation of that number, using the full notation as given in the below examples (where a lower-case "x" is used to denote multiplication).

Prime Factorisation

For those not sure of any results, I have given a full list in the attached here.

Solution next week. Best of luck!

22 comments

  1. Took me ages but here is mine:

    =IF((MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)=A2, "Prime", IF(VLOOKUP((A2/(MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)),A:B,2,0)="Prime",(MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)&"x"&(A2/(MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)), (MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)&"x"&VLOOKUP((A2/(MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=(A2/ROW(INDIRECT("2:"&A2))),0)+1)),A:B,2,0)))
  2. I certainly did not try to shorten my last one, was so happy to have a solution, here is my slightly shortened version:

    =IF((MATCH(TRUE, INT(A2/ROW(INDIRECT("2:"&A2)))=A2/ROW(INDIRECT("2:"&A2)),)+1)=A2, "Prime", IF(VLOOKUP((A2/(MATCH(TRUE, INT(A2/ROW(INDIRECT("2:"&A2)))=A2/ROW(INDIRECT("2:"&A2)),)+1)),A:B,2,)="Prime",MATCH(TRUE, INT(A2/ROW(INDIRECT("2:"&A2)))=A2/ROW(INDIRECT("2:"&A2)),)+1&"x"&(A2/(MATCH(TRUE, INT(A2/ROW(INDIRECT("2:"&A2)))=A2/ROW(INDIRECT("2:"&A2)),)+1)), MATCH(TRUE, INT(A2/ROW(INDIRECT("2:"&A2)))=A2/ROW(INDIRECT("2:"&A2)),)+1&"x"&VLOOKUP((A2/(MATCH(TRUE, INT((A2/ROW(INDIRECT("2:"&A2))))=A2/ROW(INDIRECT("2:"&A2)),)+1)),A:B,2,)))
  3. Hi Chris!

    You appear to have outwitted me here! I had not actually intended for the results of previous formulas to be used in the calculations for further rows.

    Of course, I did not state this explicitly, so I cannot fault your solution. So congratulations! Great stuff!

    However, I’m still hoping for a solution which avoids this technique (i.e. uses information already generated by the results of previous formulas), and so, to make this clear, I will amend the post such that only a value in A2 is to be considered, which of course can vary from 2 to 100.

    I don’t mean this to detract in any way from all the hard work you’ve done: your solution is faultless and uses some excellent techniques. It’s simply my fault for not being explicit in the phrasing of my question. Of course, I don’t expect you to have another go based on this new criterion, and I will of course name you as a worthy winner when I announce the results!

    Regards

  4. I appreciate that once again, I have used more or less a gimmick solution but sadly, I could not get the looping to work properly; I have a much more hideous and lengthy solution which does not use previous cells (but it is of very limited use and incredibly slow and manual). I am looking forward to hearing how to do this tidily, I suspect it is above me but I might give it another go soon.

    Chris

  5. Not at all “gimmicky”! Like I said, some very good techniques displayed indeed.

    Working with primes is difficult enough, never mind concatenating strings. So you’re to be commended for what you’ve achieved.

    In fact, the solution I have would certainly not be advisable beyond a few cells’ worth of data, such is its length. Still, we do have a limited number of techniques which we can employ to help matters somewhat, though I would not in any way call my solution ideal!

  6. This seems too hard for me ๐Ÿ˜„

    The best I could do so far is to tell if a number is PRIME. Here is one way to tell if something is PRIME in Google Sheets:

    =if(countif(find(".",A2/row(indirect("A1:A"&A2))),#VALUE!)=2,"Prime",) 

    (with ctrl+shift+enter)

    This looks like it would work in Excel, but I guess COUNTIF works differently in Excel. Here is an Excel version:

    =IF(SUM(--ISERROR(FIND(".",A2/ROW(INDIRECT("A1:A"&A2)))))=2,"Prime","") 

    (with ctrl+shift+enter)

  7. Hi again!

    It is a very long formula, but it has a repeating pattern:

    MAIN FORMULA (Not CSE for names):

    =IF(--(SUMPRODUCT(--(FLOOR(A2,ROW(INDIRECT("$1:"&INT(SQRT(A2)))))=A2))=1),"Prime",SUBSTITUTE(TRIM(Arry1&" "&Arry2&" "&Arry3&" "&Arry4&" "&Arry5&" "&Arry6)," ","x"))

    NAMES:

    Arry1:

    =1+MATCH(1,--(MOD($A2,ROW(INDIRECT("2:"&$A2-1)))=0),)

    Arry2:

    =IFERROR(1+MATCH(1,--(MOD(Sheet1!$A2/Arry1,ROW(INDIRECT("2:"&Sheet1!$A2-1)))=0),)," ")

    Arry3:

    =IFERROR(1+MATCH(1,--(MOD(Sheet1!$A2/Arry1/Arry2,ROW(INDIRECT("2:"&Sheet1!$A2-1)))=0),)," ")

    Arry4:

    =IFERROR(1+MATCH(1,--(MOD(Sheet1!$A2/Arry1/Arry2/Arry3,ROW(INDIRECT("2:"&Sheet1!$A2-1)))=0),)," ")

    Arry5:

    =IFERROR(1+MATCH(1,--(MOD(Sheet1!$A2/Arry1/Arry2/Arry3/Arry4,ROW(INDIRECT("2:"&Sheet1!$A2-1)))=0),)," ")

    Arry6:

    =IFERROR(1+MATCH(1,--(MOD(Sheet1!$A2/Arry1/Arry2/Arry3/Arry4/Arry5,ROW(INDIRECT("2:"&Sheet1!$A2-1)))=0),)," ")

    Blessings!

  8. I’m glad John had the same issues as me. There must be a way of shortening and tidying up that repeating pattern…

  9. This is a little sloppy as I’m in a hurry but:

    A2 <=100, so if A2 isn't prime it must have a prime factor <sqrt(100) or 10.

    I used:

    =IF(OR(A2=2,A2=3,A2=5,A2=7),"Prime",REPT("2x",LN(GCD(64,A2))/LN(2))&REPT("3x",LN(GCD(81,A2))/LN(3))&REPT("5x",LN(GCD(25,A2))/LN(5))&REPT("7x",LN(GCD(49,A2))/LN(7))&IF(A2/GCD(64,A2)/GCD(81,A2)/GCD(25,A2)/GCD(49,A2)=1,"",A2/GCD(64,A2)/GCD(81,A2)/GCD(25,A2)/GCD(49,A2)))

    That gives an extra "x" in the cases where the number is a multiple of the first 4 primes, and it does not label prime 5+ as Prime, but it seems like it solves a lot of the problem without too much spreadsheet magic.

    I need to think about how to fix the rest. This method will easily give the prime factorization though just by deleting the initial if. (Without the "prime" label. )

  10. @Patrick Kearney

    Ingenious, and good application of logical reasoning in order to reduce the required number of tests.

    I’ve shot myself in the foot again by imposing a restriction on the size of the value in question (<=100), since I did not actually intend for such a piecemeal approach, as ingenious as it is, to be used. Perhaps if I'd made this limit e.g. <=1,000? I imagine that you'd then simply add a further 7 clauses to test for division of the further primes up to 31?

    In any case, even this would not present a solution of unfeasible length. Perhaps if we were to set the upper limit to 10,000, however? Mind you, in that case my proposed solution would certainly not work either, and so I must conclude that, with an upper limit of 100, yours is certainly the more practical (and logical) solution, so congratulations! (On proviso that you iron out the couple of outstanding issues you currently have, of course!)

    Many thanks and regards.

  11. This formula returns a True if the number is a prime a False otherwise

    =OR(A1={2;3},SUM(--ISERR(FIND(".",A1/ROW(INDIRECT("2:"&INT(A1^0.5))))))=0)

    Now to try and do the factorisation

  12. @Ola

    Welcome to the site and many thanks for your contribution!

    Can you just clarify for readers that this formula is intended to be array-entered, I presume?

    Also, I presume that it is to be entered in row 3 somewhere, i.e. for a value of 3 in A3, then copied down? If so, what result do you get for this formula in row 4, i.e. for A4=4?

    Regards

  13. Amazing Answers ๐Ÿ™‚ Learnt a lot from this challenge. Probably too late to attempt this challenge but hre is my solution.

    =IF(OR(AND(MOD(A5,1)=0,IFERROR(MOD(A5,$A$1:A4),1)0),A5=2),"Prime",MATCH(0,MOD(A5,IFERROR((ROW($A$1:A4)-1)+SEARCH("Prime",$Q$1:Q4),"")),0)&"x"&IF(LOOKUP(GCD(A5,A5/MATCH(0,MOD(A5,IFERROR((ROW($A$1:A4)-1)+SEARCH("Prime",$Q$1:Q4),"")),0)),$A$1:A4,$Q$1:Q4)="Prime",GCD(A5,A5/MATCH(0,MOD(A5,IFERROR((ROW($A$1:A4)-1)+SEARCH("Prime",$Q$1:Q4),"")),0)),LOOKUP(GCD(A5,A5/MATCH(0,MOD(A5,IFERROR((ROW($A$1:A4)-1)+SEARCH("Prime",$Q$1:Q4),"")),0)),$A$1:A4,$Q$1:Q4)))

    Its an Array formula and I had created this in Column Q ๐Ÿ™‚

    Cheers

  14. Hi Calvin. Welcome to the site and many thanks for your kind words, and for your contribution!

    Can you just clarify in which row this formula is to be placed? Doesn’t look like it’s designed for row 2? Would guess that it’s intended for cell Q5, right? But then I tried it in that cell and copied down and got many errors as a result.

    Cheers!

  15. Hello XOR LX ๐Ÿ™‚ I just realized that for some reason, the 0 condition I had used in the 2nd logical statement of my AND statement isn’t pasted. I have rectified it now. And yes, the formula was copied from the Q5 cell. My bad :-). See the answer below:

    Kindly Paste this formula in cell Q2. It should work just fine. Please let me know your thoughts on this formula!

    =IF(OR(AND(MOD(A2,1)=0,IFERROR(MOD(A2,$A$1:A1),1)<>0),A2=2),"Prime",MATCH(0,MOD(A2,IFERROR((ROW($A$1:A1)-1)+SEARCH("Prime",$Q$1:Q1),"")),0)&"x"&IF(LOOKUP(GCD(A2,A2/MATCH(0,MOD(A2,IFERROR((ROW($A$1:A1)-1)+SEARCH("Prime",$Q$1:Q1),"")),0)),$A$1:A1,$Q$1:Q1)="Prime",GCD(A2,A2/MATCH(0,MOD(A2,IFERROR((ROW($A$1:A1)-1)+SEARCH("Prime",$Q$1:Q1),"")),0)),LOOKUP(GCD(A2,A2/MATCH(0,MOD(A2,IFERROR((ROW($A$1:A1)-1)+SEARCH("Prime",$Q$1:Q1),"")),0)),$A$1:A1,$Q$1:Q1)))

    Cheers ๐Ÿ™‚

  16. Great stuff, Calvin! Works on every example!

    I like your use of GCD here as well – very appropriate, and not often we see that function being used.

    Thanks for providing an interesting alternative – it’s never too late!

    Cheers (and sorry for the comment editing)!

  17. UDF:

    Function PrimeFact$(ByVal n&)
    Dim i&, txt$
    i = 2
    While i * i <= n
    If n Mod i Then i = i + 1 Else n = n \ i: txt = txt & "x" & i
    Wend
    If txt = "" Then PrimeFact = "Prime" Else PrimeFact = Mid$(txt, 2) & "x" & n
    End Function

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s