Friday 16 October 2015

Project Euler #3: Largest prime factor

Today I will show how to solve Project Euler Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of a given number N?
Input Format
First line contains T, the number of test cases. This is followed by T lines each containing an integer N.
Output Format
For each test case, display the largest prime factor of N.
Constraints
1≤T≤10
10≤N≤1012
Sample Input
2
10
17
Sample Output
5
17

Solution
int T = int.Parse(Console.ReadLine());
long[] numbers = new long[T];
for (int i = 0; i < T; i++)
{
    numbers[i] = Int64.Parse(Console.ReadLine());
}
for (int i = 0; i < T; i++)
{
    long num = numbers[i];
    int a = 3;
    while (num % 2 == 0)
      num = num / 2;
    if (num == 1)
      num = 2;
    while (a <= Math.Sqrt(num))
    {
      if (num % a == 0)
      {
        num = num / a;
        continue;
                        //a --;
      }
        a = a + 2;
    }
      Console.WriteLine(num);
}


No comments:

Post a Comment