We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #12: Highly divisible triangular number
  4. Discussions

Project Euler #12: Highly divisible triangular number

Sort by

recency

|

123 Discussions

|

  • valogonor
     + 0 comments

    Here's an efficient solution in Python that takes advantage of the fact that the formula for the nth triangular number is n * (n+1) // 2 and the fact that n and n + 1 are coprime:

    def count_factors(num):
    ans = 0
    for i in range(1, int(num**.5) + 1):
        if num % i == 0:
            ans += 1 if i * i == num else 2
    return ans
    
def solve(mindivs):
    n = 1
    while True:
        trinum = n * (n + 1) // 2
        if n % 2 == 0:
            divcount = count_factors(n // 2) * count_factors(n + 1)
        else:
            divcount = count_factors((n+1)//2) * count_factors(n)
        if divcount > mindivs:
            return trinum
        n += 1

t = int(input())
for _ in range(t):
    n = int(input())
    print(solve(n))

  • yonahel
     + 0 comments

    Haskell

    import Control.Applicative
import Control.Monad
import System.IO
import Prelude
import Data.List

isqrt :: Int -> Int -- Thanks StackOverflow
isqrt = ceiling . sqrt . fromIntegral

triangle_num :: Int -> Int
triangle_num n = (n * (n + 1)) `div` 2

triangle_nums = map triangle_num [1..]

primes = 2 : [i | i <- [3..1000],  
              and [rem i p > 0 | p <- takeWhile (\p -> p^2 <= i) primes]]

num_subdivisions :: Int -> Int -> Int -> Int
num_subdivisions num divisor rem
    | num `mod` divisor /= 0 = rem
    | otherwise = num_subdivisions (num `div` divisor)  divisor (rem+1)

num_divisors :: Int -> Int
num_divisors 1 = 1
num_divisors n = product [((num_subdivisions n x 0) + 1) | x <- (filter (<= ((isqrt n) + 1)) primes), n `mod` x == 0]

smallestTri :: Int -> [Int] -> Int
smallestTri n xs
    | num_divisors (head xs) > n = head xs
    | otherwise = smallestTri n (tail xs)

main :: IO ()
main = do
    t_temp <- getLine
    let t = read t_temp :: Int
    forM_ [1..t] $ \a0  -> do
        n_temp <- getLine
        let n = read n_temp :: Int
        let smallTri = smallestTri n triangle_nums
        print(smallTri)

  • vishwasshivamog1
     + 0 comments

    include

    include

    include

    using namespace std;

    int main() { const int MAX_PRIMES = 1000; vector primes(MAX_PRIMES, 0); primes[0] = 2; primes[1] = 3; primes[2] = 5; primes[3] = 7; int count1 = 4; long long num = 9; while(count1 < MAX_PRIMES) { bool isprime = true; int sqrt_num = sqrt(num);

        for(int i = 0; primes[i] <= sqrt_num && i < count1; i++) {
        if(num % primes[i] == 0) {
            isprime = false;
            break;
        }
    }
    if(isprime) {
        primes[count1] = num;
        count1++;
    }
    num += 2;
}

int t;
cin >> t;
while(t--) {
    long long n;
    cin >> n;

    long long sum = 1;
    long long result = 1;
    long long j = 2;

    while(true) {
        sum += j;
        long long temp = sum;
        result = 1;  
        for(int k = 0; k < count1 && primes[k] > 0; k++) {
            int count2 = 1;
            while(temp % primes[k] == 0) {
                temp /= primes[k];
                count2++;
            }
            result *= count2;
            if(temp == 1) {
                break;
            }
        }
        if(result > n) {
            break;
        }
        j++;
    }
    cout << sum << endl;
}
return 0;

    }

  • CS_2212256_T
     + 0 comments

    BY TANUSHREE SARKAR

    import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        int[] primes = new int[1000];
        primes[0] = 2;
        primes[1] = 3;
        primes[2] = 5;
        primes[3] = 7;
        int count1 = 4;
        int num = 9;

        while (num <= 1000000) {
            boolean isPrime = true;
            for (int i = 0; i < count1; i++) {
                if (num % primes[i] == 0) {
                    isPrime = false;
                    break;
                } else if (primes[i] > (num / 2)) {
                    break;
                }
            }
            if (isPrime) {
                primes[count1] = num;
                count1++;
                if (count1 == 1000) {
                    break;
                }
            }
            num += 2;
        }

        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            long n = in.nextLong();

            int j = 2;
            long result = 1;
            long sum = 1;
            int count2 = 1;

            while (true) {
                sum += j;
                long temp = sum;

                for (int k = 0; k < 1000; k++) {
                    count2 = 1;
                    while (true) {
                        if (temp % primes[k] == 0) {
                            temp /= primes[k];
                            count2++;
                        } else {
                            break;
                        }
                    }
                    result *= count2;
                    if (temp == 1) {
                        break;
                    }
                }
                if (result > n) {
                    break;
                } else {
                    result = 1;
                }
                j++;
            }
            System.out.println(sum);
        }
    }
}

  • mittalmanish881
     + 0 comments

    import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

    public class Solution {

    public static void main(String[] args) {

    int [] primes = new int[1000];

    primes[0] = 2; primes[1] = 3; primes[2] = 5; primes[3] = 7; int count1 = 4; int num = 9;

    int i = 0;

    mainl: while(num <= 1000000) {

    for(i=0;i<count1;i++) {
    if(num % primes[i] == 0) {
        break;
    }
    else if(primes[i] > (num/2)) {
        primes[count1] = num;
        count1++;

        if(count1 == 1000) {
            break mainl;
        }
        break;
    }
}

if(i == count1) {
    primes[count1] = num;
    count1++;

    if(count1 == 1000) {
        break mainl;
    }
}

num += 2;

    }

    Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ long n = in.nextLong();

    int j = 2;

    long result = 1; long sum = 1; int count2 = 1;

    while(true) {

    sum += j;
long temp = sum;

loop1:
for(int k=0;k<1000;k++) {
    count2 = 1;
    while(true) {

        if(temp % primes[k] == 0) {
            temp /= primes[k];
            count2++;
        }
        else {
            break;
        }
    }
    result *= count2;
    if(temp == 1) {
        break loop1;
    }
}
if(result > n) {
    break;
}
else {
    result = 1;
}

j++;

    }

    System.out.println(sum); }}}