-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathProblem3.0 - Largest Prime Factor.html
120 lines (115 loc) · 6.35 KB
/
Problem3.0 - Largest Prime Factor.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
<html>
<head>
<title>Project Euler, Problem 3.0: Largest Prime Factor</title>
<style>
#explanation {
visibility: hidden;
}
#problem {
text-align: center;
border: 2px solid black;
border-radius: 5px;
width: 150px;
padding: 2px;
}
</style>
</head>
<body>
<p>
The prime factors of 13195 are 5, 7, 13 and 29.
</br></br>
What is the largest prime factor of the number 600851475143 ?.
</p>
<div id="problem">
<input id="answer" type="number" name="Answer" style="margin-bottom: 5px" />
<br />
<input type="button" value="Project Euler" onclick="projectEulerProblem3()" />
</div>
<div id="explanation">
</br>
<div id="totalTime"></div>
<p>
To solve this, I used a brute force technique. Instead of including a test for primality, I included a list of primes.
</br></br>
I check each prime in my list to see if it divides my original number. If it does, I push that prime
into my list of factors and recheck the number (recently divided by the factor) against the list of primes
again and again until my original number is equal to 1.
<br /><br />
I currently have every prime up to 3511 in my prime number array.
</p>
</div>
</body>
<script>
//This array holds all the primes. I use these to divide my test number by
var primes = [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, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653,
659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783,
1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993,
1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749,
2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957,
2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187,
3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373,
3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511];
//This is an array to hold my factors
var numberFactors = [];
//var factorCeiling = Math.floor(Math.sqrt(number));
//this is an empty function (for now). It will be used to test the primality of a number as soon as I figure out how to do that...
function checkIfPrime() {
}
//This is my brute force factorization algorithm
function projectEulerProblem3() {
var startTime = new Date();
//This gets the number to be factored
var number = document.getElementById("answer").value;
//This variable breaks my while loop if I run through all the primes in my array w/out finding a factor
var abandonShip = false;
//This loop runs as long as the number being tested is not in my array of primes
//If it were, I wouldn't find a factor and I can stop, because I've found the largest factor
while (!primes.includes(number)) {
//If we've factored down to 1, then we've found all the factors
if (number < 2) {
break;
}
//This is the brute force part of finding the factors
//primeIndex points to an element in the primes array
for (primeIndex = 0; primeIndex < primes.length; primeIndex++) {
//if our number devides cleanly into the current prime, we divide and push the factor into numberFactors
if ((number % primes[primeIndex]) === 0) {
number /= primes[primeIndex];
numberFactors.push(primes[primeIndex]);
//If we find a factor, we want to break the for loop and start the process over in the while loop
break;
} else {
}
//If, having gone through all of the primes in my array, I don't find a factor, I break the while loop
//to avoid an infinite loop
if (primeIndex === (primes.length - 1)) {
abandonShip = true;
break;
}
}
if (abandonShip) {
break;
}
}
//This puts the final number into the numberFactors array
numberFactors.push(number);
var endTime = new Date();
var totalTime = endTime - startTime;
//This prints the final list of factors to the HTML
document.getElementById("problem").innerHTML = numberFactors;
document.getElementById("totalTime").innerHTML = totalTime + " ms";
document.getElementById("explanation").style.visibility = "visible";
}
</script>
</html>