It looks like you're new here. If you want to get involved, click one of these buttons!

- 2.2K All Categories
- 1.7K The Midnight Age
- 43 Announce posts
- 88 Newbies
- 4 Class Guides
- 581 Harpy's Head Tavern
- 37 Echo Canyon
- 207 Self-Affirmations
- 138 Town Crier
- 109 The Exchange
- 126 Sparring Grounds
- Combat Guides
- 21 Combat Logs
- 138 Idea Box
- 8 Liaisons
- 381 Roleplay Logs
- 82 Aetolia Development
- 5 The Void
- 606 Miscellaneous
- 8 Announcements
- 328 OOC Chat
- 174 Tech Talk
- 31 Scripts

So guys, lately I've been spending a bit of time going through math problems and solving them. I personally have found it fun and think it'd be enjoyable to discuss solutions and such to the problems with others similarly inclined. Below is the link!

https://projecteuler.net/archives

https://projecteuler.net/archives

1

## Comments

96✭✭✭985✭✭✭✭✭96✭✭✭The main appeal of this is that it saves on the memory required by Eratosthenes' sieve. I also decided to begin the iteration at 3 and add in increments of 2, so as only to test odd numbers and further reduce the time spent on calculation. As each prime factor is found, the problem recurses, until it reaches a base case where a given number is the maximum prime factor, as determined by the square root test - this is then passed back upward to the top. I've tested it on smaller numbers as well as 600851475143, 67280421310721, and 67280421310719 - good results in all cases.

As solutions go, I'm proud of this one.

`public static long getPrimeFactor(long n) { System.out.println("Initial Input: " + n); long test = n; /* We initialize the max as the number itself - if, in the loop below, we reach the bound without this value having changed, we know it's time to stop. */ long max = n; boolean stripped = false; if (test % 2 == 0) { System.out.println("Stripping out factors of 2."); } while (test % 2 == 0) { test /= 2; stripped = true; } if (stripped) { if (test == 1) { max = 2; } else { max = test; } System.out.println("Value stripped down to " + test); } /* The square root is important for cases in which this function actually does handle a prime. Why? Because the square root is the cutoff at which we must have found a multiple by now, and it's conveniently a mere fraction of the larger number. If our maximum (see below) remains the number itself, we're not going to find anything above the square root that will cleanly divide out of it. */ long bound = (long)Math.sqrt(test); System.out.println("Bound: " + bound); /* The bound is offset by one to account for rounding issues that might have resulted from the cast above. Math.sqrt returns a double - we need a whole number. */ for (long i = 3; i <= bound + 1; i += 2) { if (test % i == 0) { test /= i; System.out.println("Divisor Found: " + i + " divides out for " + test); System.out.println("\nRecursing Once More"); max = getPrimeFactor(test); break; } if (test < i) { System.out.println("Breaking - testing number now under iterative value; highest factor found. Passing " + max + " to higher function.\n"); return max; } if (i >= bound && max == n) { System.out.println("Breaking - bound reached; highest factor found. Passing " + max + " to higher function.\n"); return max; } } return max; }`

1,990✭✭✭✭✭985✭✭✭✭✭96✭✭✭(2^4)*(3^2)*5*7*11*13*17*19 = 232792560