From 6aa02212cd6dfbb492fa1f70b60a4fe3d48892e5 Mon Sep 17 00:00:00 2001 From: mjf Date: Tue, 4 Feb 2020 12:11:30 -0500 Subject: cleanup and added more c examples: --- 10001prime.py.orig | 30 -------------------------- bigfactors2.py.orig | 32 ---------------------------- collatz | Bin 16688 -> 16696 bytes collatz.c | 18 +++++----------- collatz.py.orig | 24 --------------------- fib | Bin 0 -> 16776 bytes fib.c | 33 +++++++++++++++++++++++++++++ fib.py.orig | 33 ----------------------------- largestprime | Bin 0 -> 16648 bytes largestprime.c | 21 ++++++++++++++++++ largestprime.py | 43 +------------------------------------ largestprime.py.orig | 55 ------------------------------------------------ palindrome.py.orig | 40 ----------------------------------- productofdigits.py.orig | 18 ---------------- smallmult.py.orig | 26 ----------------------- sumexp.py.orig | 10 --------- sumofprimes.py.orig | 44 -------------------------------------- sumsq.py.orig | 27 ------------------------ 18 files changed, 60 insertions(+), 394 deletions(-) delete mode 100644 10001prime.py.orig delete mode 100644 bigfactors2.py.orig delete mode 100644 collatz.py.orig create mode 100755 fib create mode 100644 fib.c delete mode 100644 fib.py.orig create mode 100755 largestprime create mode 100644 largestprime.c delete mode 100644 largestprime.py.orig delete mode 100644 palindrome.py.orig delete mode 100644 productofdigits.py.orig delete mode 100644 smallmult.py.orig delete mode 100644 sumexp.py.orig delete mode 100644 sumofprimes.py.orig delete mode 100644 sumsq.py.orig diff --git a/10001prime.py.orig b/10001prime.py.orig deleted file mode 100644 index ecaa8cd..0000000 --- a/10001prime.py.orig +++ /dev/null @@ -1,30 +0,0 @@ -import PIL, math - -#Problem 7 - 10,001st prime - -#returns a list of every prime up to a certain number -def listprimes(number): - primes = [] - if (number <=1): - return [1] - a = [1] * number - a[0]=0 - a[1]=0#1 and 0 are not prime - ##Sieve of eratosthenes - for i in range(2,int(math.ceil(math.sqrt(number)))): - if(a[i]==1): - j = i**2 #cross out all the multiples of i, starting with its square - while(j < number): - a[j] = 0 - j+=i - - for k in range(2, number): - #is prime - if(a[k]==1): - primes.append(k) - return primes - -out_list = listprimes(1000000) -#print(out_list) -#return 10,001th prime factor -print(out_list[10000]) diff --git a/bigfactors2.py.orig b/bigfactors2.py.orig deleted file mode 100644 index 41bc13d..0000000 --- a/bigfactors2.py.orig +++ /dev/null @@ -1,32 +0,0 @@ -import PIL, math - -#Problem 12 Highly divisible triangular number -#finds the first number with over 500 factors - -def countfactors(num): - factors = 0 - ### we only need to know about the FIRST HALF of factors, - ##one factor implies a second - root = int(math.ceil(math.sqrt(num))) - divs = range(1, root) - for d in divs: - if(num%d == 0): - factors += 2 - - #Correction if the number is a perfect square - if (root * root == num): - factors-=1 - return factors - - -#### MAIN ##### -i=1 -k=1 -j = 0 -while(k < 500): - j += i - k=countfactors(j) - print(str(j) + " has " + str(k) + " factors") - i += 1 - -print("Ding! Ding! {} has over 500 factors, wow!".format(j)) diff --git a/collatz b/collatz index 75c5d45..37da709 100755 Binary files a/collatz and b/collatz differ diff --git a/collatz.c b/collatz.c index 5bbb783..ec77af6 100644 --- a/collatz.c +++ b/collatz.c @@ -1,19 +1,13 @@ #include #include #include -#include +// In C, it's immediately obvious my python solution is inefficient -// Temporary storage chain -//long int *chain; -// The longest sequence found so far -//long int *seq; - -// Size of the above arrays +// For keeping track of the length of sequences +// c is a temporary counter, s changes when c reaches a new maximum long int c = 0; long int s = 0; long int collatz(long int seed){ - //chain = (long int *) realloc (chain, c * sizeof(long int)); - //chain[c - 1] == seed; c++; if(seed == 1) return 0; @@ -21,19 +15,17 @@ long int collatz(long int seed){ seed = seed / 2; else seed = 3 * seed + 1; - //collatz(seed); + collatz(seed); } int main(){ for(long int i = 1; i < pow(10, 6); i++){ c = 0; - //chain = (long int *) malloc(c * sizeof(long int)); collatz(i); - printf("%d \n", i); if(c > s){ s = c; } } - printf("Has %d numbers \n", s); + printf("The longest sequence has %d numbers \n", s); return 0; } diff --git a/collatz.py.orig b/collatz.py.orig deleted file mode 100644 index 404a2ed..0000000 --- a/collatz.py.orig +++ /dev/null @@ -1,24 +0,0 @@ -import PIL, math - -#Problem 14 Longest Collatz sequence -#Note, a little slow, takes about 15 seconds. -#There is probably a more efficient solution out there -chain = [] -biggo = [] - -def collatz(seed): - chain.append(seed) - if(seed == 1): return 0 - if(seed%2 == 0): - seed = seed/2 - else: - seed = 3*seed +1 - collatz(seed) - -for n in range(1,pow(10,6)): - collatz(n) - if(len(chain)>len(biggo)): - biggo = chain - chain = [] -print(biggo) -print("Has " + str(len(biggo)) +" numbers.") diff --git a/fib b/fib new file mode 100755 index 0000000..e9b1b3b Binary files /dev/null and b/fib differ diff --git a/fib.c b/fib.c new file mode 100644 index 0000000..915fccd --- /dev/null +++ b/fib.c @@ -0,0 +1,33 @@ +#include +#include +#include + +const long int MAX = 4 * pow(10, 6); +int *fib; + +int main(){ + // Intialize sequence with first two terms + fib = (int *) malloc (2 * sizeof(int)); + fib[0] = 1; + fib[1] = 1; + + // loop counter + int k = 1; + // sum of even terms + int sum = 0; + //next term in sequence + int next; + while(1){ + next = fib[k] + fib[k - 1]; + printf("%d\n", next); + if(next > MAX) + break; + if(next % 2 == 0) + sum += next; + k++; + fib = (int *) realloc (fib, (k + 1) * sizeof(int)); + fib[k] = next; + } + printf("The sum of the even terms is %d\n", sum); + return 0; +} diff --git a/fib.py.orig b/fib.py.orig deleted file mode 100644 index 77b32fa..0000000 --- a/fib.py.orig +++ /dev/null @@ -1,33 +0,0 @@ -import PIL, math -MAX = 4*10**6 - -#Problem 2 Even Fibonnacci numbers -fib = [1, 1] - -k=1; -while (True): - n = fib[k] + fib[k-1] - if(n>MAX): - break - else: - fib.append(n); - k+=1 - -c=0 -for i in fib: - num = str(i) - print(num + " ", end='') - c+=1 - if(c%10==0): - print() - -print() - -print("The sum is: " + str(sum(fib))) - -s=0 -for i in fib: - if (i%2==0): - s+=i - -print("The sum of the even terms is: " + str(s)) diff --git a/largestprime b/largestprime new file mode 100755 index 0000000..c2afe6f Binary files /dev/null and b/largestprime differ diff --git a/largestprime.c b/largestprime.c new file mode 100644 index 0000000..bf98414 --- /dev/null +++ b/largestprime.c @@ -0,0 +1,21 @@ +#include +#include + +long lpf(long num){ + long factor = 2; + while(num > factor){ + if(num % factor == 0){ + num = num / factor; + factor = 2; + } + else{ + factor ++; + } + } + return factor; +} + +int main(){ + printf("%d\n", lpf(600851475143)); + return 0; +} diff --git a/largestprime.py b/largestprime.py index fa53dc5..387de01 100644 --- a/largestprime.py +++ b/largestprime.py @@ -1,47 +1,6 @@ import PIL import math -import numpy as np # Problem 3 Largest Prime Factor - -###INEFFICIENT METHODS### -# def isPrime(number): -# if (number <=1): -# return False -# for i in range(2,number): -# if(number%i==0): -# return False -# return True - -# def prime_factors(number): -#primes = [] -# for i in range(number, 2, -1): -# if(number%i==0): -# if (isPrime(i)): -# return i -# return primes - - -def prime_factors(number): - primes = [] - if (number <= 1): - return [1] - a = np.ones(number) - a[0] = 0 - a[1] = 0 # not prime - for i in range(2, int(math.ceil(math.sqrt(number)))): - if(a[i] == 1): - j = i**2 # cross out all the multiples - while(j < number): - a[j] = False - j += i - - for k in range(2, number): - # is prime is a factor - if(a[k] == 1) and (number % k == 0): - primes.append(k) - return primes - - def lpf(number): factor = 2 while (number > factor): @@ -54,4 +13,4 @@ def lpf(number): out = lpf(600851475143) -print out +print(out) diff --git a/largestprime.py.orig b/largestprime.py.orig deleted file mode 100644 index fa39904..0000000 --- a/largestprime.py.orig +++ /dev/null @@ -1,55 +0,0 @@ -import PIL, math -import numpy as np -#Problem 3 Largest Prime Factor - -###INEFFICIENT METHODS### -#def isPrime(number): -# if (number <=1): -# return False -# for i in range(2,number): -# if(number%i==0): -# return False -# return True - -#def prime_factors(number): - #primes = [] - #for i in range(number, 2, -1): - #if(number%i==0): - #if (isPrime(i)): - #return i - #return primes - - - -def prime_factors(number): - primes = [] - if (number <=1): - return [1] - a = np.ones(number) - a[0]=0 - a[1]=0#not prime - for i in range(2,int(math.ceil(math.sqrt(number)))): - if(a[i]==1): - j = i**2 #cross out all the multiples - while(j < number): - a[j] = False - j+=i - - for k in range(2, number): - #is prime is a factor - if(a[k]==1) and (number%k==0): - primes.append(k) - return primes - -def lpf(number): - factor = 2 - while (number > factor): - if(number % factor == 0): - number = number/factor - factor = 2 - else: - factor +=1 - return factor - -out = lpf(600851475143) -print out diff --git a/palindrome.py.orig b/palindrome.py.orig deleted file mode 100644 index 9690553..0000000 --- a/palindrome.py.orig +++ /dev/null @@ -1,40 +0,0 @@ -import PIL, math - -#Problem 4 - Palindrome Products - -def isPalindrome(number): - numchar = str(number) - middle = len(numchar)/2 - face = numchar[:middle] - ref = numchar[len(numchar):middle-1:-1] - if(face == ref): - return True - else: - return False - -def findProduct(number): - for i in range(999,100,-1): - for j in range(999,100,-1): - if(i*j==number): - return [i,j] - -def findMaxPalindrome(): - large = 0 - for i in range(999,100,-1): - for j in range(999,100,-1): - test = i*j - if(isPalindrome(test) and test > large): - large = test - return large - -answer = findMaxPalindrome() -print(answer) -print("The factors are: " + str(findProduct(answer))) -#x = input("Type a palindromic number: ") - -#if(isPalindrome(x)): - #print "The factors are: " + str(findProduct(x)) -#else: - #print "not a palindrome" - - diff --git a/productofdigits.py.orig b/productofdigits.py.orig deleted file mode 100644 index ddd5edc..0000000 --- a/productofdigits.py.orig +++ /dev/null @@ -1,18 +0,0 @@ -import PIL, math -import numpy as np - -#Problem 8 - largest Product in a series -bigBoy=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450 - -def parseNum(x, r): - search = str(x) - maxi = 0 - for ch in range(0,len(search)-r): - prod = int(search[ch]) - for dig in range(ch+1, ch+r): - prod*=int(search[dig]) - if (prod > maxi): - maxi = prod - return maxi - -print(parseNum(bigBoy, 13)) diff --git a/smallmult.py.orig b/smallmult.py.orig deleted file mode 100644 index d672ef0..0000000 --- a/smallmult.py.orig +++ /dev/null @@ -1,26 +0,0 @@ -#Problem 5 smallest multiple -#2520 is the smallest number that can be divided by -#each of the numbers from 1 to 10 without any remainder. -#What is the smallest positive number that is evenly divisible -#by all of the numbers from 1 to 20? - -import PIL, math - -def isDivisible(num, divisors): - divisible = True - for j in divisors: - if(num%j !=0): - divisible = False - break - return divisible - -divs = range(1,21) - -found = False -start = 2520 -while (not found): - start+=20 - found = isDivisible(start,divs) - -print(start) -print(str(isDivisible(start, divs))) diff --git a/sumexp.py.orig b/sumexp.py.orig deleted file mode 100644 index 90dd2da..0000000 --- a/sumexp.py.orig +++ /dev/null @@ -1,10 +0,0 @@ -import PIL, math -#Problem 16 Power digit sum -n = 2**1000 -strn = str(n) -s = 0 - -for i in strn: - s += int(i) - -print(s) diff --git a/sumofprimes.py.orig b/sumofprimes.py.orig deleted file mode 100644 index 3799e94..0000000 --- a/sumofprimes.py.orig +++ /dev/null @@ -1,44 +0,0 @@ -import PIL, math - -#Problem 10 sum of primes -###INEFFICIENT### -#def isPrime(number): -# if (number <=1): -# return False -# for i in range(2,number): -# if(number%i==0): -# return False -# return True - -#def prime_factors(number): - #primes = [] - #for i in range(number, 2, -1): - #if(number%i==0): - #if (isPrime(i)): - #return i - #return primes - - - -def prime_factors(number): - primes = [] - if (number <=1): - return [1] - a = [1] * number - a[0]=0 - a[1]=0#not prime - for i in range(2,int(math.ceil(math.sqrt(number)))): - if(a[i]==1): - j = i**2 #cross out all the multiples - while(j < number): - a[j] = False - j+=i - - for k in range(2, number): - #is prime - if(a[k]==1): - primes.append(k) - return primes - -out = prime_factors(2000000) -print(str(sum(out))) diff --git a/sumsq.py.orig b/sumsq.py.orig deleted file mode 100644 index e5e8988..0000000 --- a/sumsq.py.orig +++ /dev/null @@ -1,27 +0,0 @@ -#The sum of the squares of the first ten natural numbers is, -#12 + 22 + ... + 102 = 385 -#The square of the sum of the first ten natural numbers is, -#(1 + 2 + ... + 10)2 = 552 = 3025 -#Hence the difference between the sum of the squares -#of the first ten natural numbers and the square of the sum is -#Find the difference between the sum of the squares of the first -#one hundred natural numbers and the square of the sum. - -import PIL, math - -nums = range(1,11) -numsq = range(1,11) - -for i in nums: - i = i*i - -print(nums) -print(numsq) - -sum1 = (sum(nums)**2) -sum2 = (sum(numsq)) - -print("The sum squared is: " + str(sum1)) -print("The sum of the squares is: " + str(sum2)) - -print("The difference is: " + str(abs(sum2-sum1))) -- cgit v1.2.3