online compiler and debugger for c/c++

code. compile. run. debug. share.
Source Code    Language
#!/bin/python3 import math import os import random import re import sys import time import math def gcd(a, b): """Calculate the Greatest Common Divisor of a and b. Unless b==0, the result will have the same sign as b (so that when b is divided by it, the result comes out positive). """ while b: a, b = b, a%b return a def is_good(a, b): return gcd(a, b) > 1 def smallest_split(val): val = val bfs_list = [(0, 0)] visited = set() # O(N) for at, steps in bfs_list: if at == len(val): return steps # O(N): so O(N^2 overall). for i in range(at, len(val)): if i not in visited and is_good(val[at], val[i]): visited.add(i) bfs_list.append((i + 1, steps + 1)) t0 = [4447, 631, 5381, 4259, 5471, 2693, 4357, 3613, 4001, 431, 3559, 7459, 5623, 6329, 4649, 1051, 331, 4567, 4231, 2053, 2749, 709, 4549, 4091, 5407, 4297, 6521, 6469, 5059, 5209, 3803, 3919, 163, 4621, 4729, 5107, 3761, 4793, 5711, 4871, 4423, 3709, 3313, 4211, 1747, 6869, 1993, 7573, 2399, 3617, 2753, 7309, 613, 3821, 2543, 353, 4133, 4057, 1279, 1783, 4679, 601, 5237, 6569, 4721, 151, 5669, 7873, 727, 5479, 7, 5683, 1093, 7481, 3739, 941, 3319, 5923, 7219, 4663, 379, 569, 541, 73, 5981, 3037, 6301, 1597, 5843, 4519, 5821, 1429, 7687, 4079, 2137, 4493, 3779, 3719, 2339, 3253, 1877, 1973, 7121, 3581, 1433, 2089, 7547, 3847, 4157, 2897, 967, 3361, 5443, 5851, 547, 1249, 3229, 6007, 3049, 563, 1399, 227, 1103, 4703, 521, 4153, 233, 311, 1097, 6389, 3191, 1619, 7247, 1571, 4003, 3, 1931, 191, 5741, 997, 7649, 6563, 5749, 5641, 2683, 5387, 167, 7883, 1153, 1913, 4013, 3271, 7583, 2963, 5503, 3637, 1979, 2579, 7151, 769, 127, 149, 6133, 439, 787, 6257, 5569, 6607, 6203, 5441, 6659, 389, 4723, 739, 1489, 3203, 3877, 241, 3019, 3659, 2927, 3499, 2719, 3793, 1367, 5099, 5009, 4993, 2161, 1831, 4253, 3511, 5147, 3931, 4813, 3631, 5813, 6271, 6173, 7853, 3163, 3061, 6737, 4957, 2069, 659, 3797, 3359, 293, 5657, 2953, 6079, 2671, 179, 307, 3727, 977, 7537, 2243, 6571, 2549, 2557, 6037, 2203, 587, 1901, 7487, 907, 7027, 367, 1091, 577, 2593, 3623, 1721, 5987, 6373, 2791, 2293, 1427, 5651, 7523, 2837, 1657, 4931, 4349, 1471, 7127, 6361, 4673, 1327, 953, 6047, 19, 4441, 6661, 3371, 2267, 6217, 2087, 2347, 1361, 7817, 1039, 7253, 7561, 7193, 4159, 1559, 1223, 6581, 101, 4373, 5227, 3331, 3767, 4817, 5827, 5323, 4327, 2843, 1259, 3881, 7213, 193, 5333, 6983, 983, 877, 2411, 1847, 5399, 3541, 1607, 3373, 5897, 4591, 4967, 2477, 473, 7591, 61, 7621, 1579, 5519, 1123, 1171, 2797, 3907, 1483, 5717, 6229, 3259, 1301, 6997, 2269, 3119, 83, 463, 5591, 2003, 239, 443, 2393, 313, 3083, 6977, 7477, 5531, 7753, 2609, 2281, 2251, 2063, 401, 7717, 1997, 2437, 7793, 6829, 4463, 6833, 7603, 1181, 53, 4451, 1447, 1277, 2591, 2467, 5581, 7589, 3023, 4229, 5279, 733, 5939, 6689, 6343, 6089, 6317, 1693, 1627, 1247, 7307, 5839, 4637, 4397, 1439, 4483, 7691, 1511, 571, 2221, 6991, 3697, 971, 257, 919, 1789, 6263, 157, 821, 5003, 1061, 6793, 5231, 7541, 5791, 5153, 3769, 1321, 1381, 811, 673, 3571, 4363, 6367, 3329, 71, 4127, 2273, 5189, 5413, 5171, 5021, 6551, 4943, 181, 223, 3929, 7741, 647, 6871, 7549, 2539, 1999, 5743, 757, 4111, 599, 853, 6143, 4201, 6067, 5113, 6131, 4951, 6529, 4903, 3299, 4987, 1889, 2531, 839, 7879, 6673, 3467, 499, 1583, 5849, 4027, 3733, 4049, 6653, 523, 947, 4657, 1759, 5807, 7069, 67, 5779, 461, 719, 4457, 1151, 7079, 3947, 5879, 6113, 617, 3943, 3469, 7013, 2917, 3343, 251, 5563, 5783, 3433, 107, 7297, 3911, 5953, 661, 2341, 6763, 6043, 6967, 2377, 6379, 4481, 1019, 2, 5011, 1733, 2039, 3593, 7159, 1409, 5087, 1951, 1021, 6481, 1213, 1297, 2029, 1907, 1291, 2689, 5417, 347, 857, 5693, 2351, 5483, 7211, 2819, 2153, 3257, 211, 3461, 4861, 7901, 2699, 5101, 6959, 6827, 5659, 5281, 2143, 1543, 2381, 6247, 5233, 487, 5737, 137, 6899, 6553, 4339, 3391, 5881, 263, 1231, 3067, 4243, 1871, 1637, 863, 4643, 5303, 797, 2729, 4523, 4409, 4787, 229, 31, 3187, 7907, 7103, 433, 5167, 2473, 1723, 1741, 2083, 7703, 1049, 7643, 1811, 2441, 467, 17, 3701, 1201, 7757, 5051, 3557, 5119, 1549, 4751, 2767, 2333, 6359, 2383, 4639, 6703, 2909, 5903, 1609, 5273, 4513, 2879, 2311, 4691, 1879, 6779, 6151, 2207, 7529, 4783, 2861, 4759, 929, 4093, 2789, 2939, 4547, 317, 5653, 7321, 2707, 6637, 6421, 677, 3137, 6719, 2713, 7129, 7877, 6311, 6599, 479, 7457, 4273, 3923, 1873, 4019, 2657, 2521, 2503, 4801, 641, 827, 37, 7451, 3089, 23, 79, 1523, 6857, 269, 3323, 4073, 4909, 5867, 2011, 3671, 3221, 2687, 7043, 5927, 1987, 97, 6619, 4831, 4651, 1423, 7243, 6121, 6911, 2969, 3517, 4261, 6287, 4241, 197, 2099, 2833, 859, 2731, 397, 6199, 2389, 7369, 6863, 7207, 7333, 4937, 3833, 7699, 6823, 6781, 3583, 2551, 1487, 1787, 5, 1013, 4219, 4597, 1453, 1229, 887, 3539, 2617, 3917, 4799, 373, 2663, 7177, 1163, 7489, 1823, 1069, 2903, 1667, 4517, 2017, 2447, 3853, 5351, 4337, 409, 1697, 2801, 7607, 4289, 7001, 2081, 7237, 5521, 3347, 6491, 7681, 199, 2111, 5437, 6733, 1801, 1009, 7019, 5347, 3389, 6449, 7789, 3863, 7499, 6197, 6701, 2287, 3121, 6791, 773, 457, 6337, 3691, 5869, 281, 1567, 2423, 6961, 7727, 2131, 5081, 5647, 643, 7057, 3491, 6679, 3169, 6947, 383, 1663, 7517, 3181, 829, 1499, 2711, 691, 751, 6971, 4271, 113, 6691, 991, 5639, 6211, 2851, 1621, 3463, 3607, 2179, 5557, 4177, 5449, 4973, 7039, 7867, 4999, 7433, 2357, 2309, 7823, 7331, 6547, 1319, 1217, 1459, 3413, 109, 3079, 5501, 619, 1613, 1063, 3533, 4507, 7723, 5297, 7577, 5861, 593, 4099, 6011, 5309, 4391, 3449, 4889, 1129, 3643, 2027, 1531, 1283, 809, 6299, 5197, 2371, 3251, 359, 6803, 13, 5179, 7669, 6427, 5393, 6029, 7283, 3407, 3001, 607, 5801, 2999, 3547, 6053, 131, 271, 4129, 6451, 7559, 2297, 491, 911, 2633, 2803, 349, 5573, 6323, 173, 3011, 4051, 2459, 557, 2677, 7393, 6101, 1187, 4421, 683, 41, 2971, 3301, 1949, 1303, 2857, 4283, 3167, 4561, 1861, 1193, 3527, 1481, 5039, 2777, 7187, 7841, 2129, 7351, 5527, 89, 3217, 5689, 6353, 47, 4919, 6949, 6883, 5701, 139, 1307, 1087, 503, 4583, 1699, 4733, 7349, 7673, 2957, 1033, 1601, 7759, 2237, 1451, 3889, 449, 3673, 2887, 1753, 823, 5477, 277, 6841, 653, 5023, 1709, 3109, 2621, 4021, 5507, 2239, 6577, 7507, 1493, 1373, 337, 3823, 7919, 3209, 4933, 5077, 6269, 5431, 283, 7411, 103, 6917, 2647, 7639, 421, 1867, 3041, 6221, 5261, 6277, 1777, 761, 3967, 883, 2113, 6091, 419, 2741, 3457, 701, 6761, 7417, 881, 6073, 3851, 4789, 6397, 7229, 4603, 1031, 3529, 4007, 1289, 5857, 1669, 1237, 509, 1933, 5419, 1553, 743, 43, 4139, 2659, 4877, 937, 2417, 6473, 6907, 6163, 1109, 7829, 4217, 3307, 2213, 59, 1117, 2141, 3989, 4969, 7109, 6709, 3677] print(smallest_split(t0))

Compiling Program...

Command line arguments:
Standard Input: Interactive Console Text
×

                

                

Program is not being debugged. Click "Debug" button to start program in debug mode.

#FunctionFile:Line
VariableValue
RegisterValue
ExpressionValue