October 2005 Problem 'bigfact' Analysis

The goal is to find the highest prime factor of an integer N.

This can be solved very quickly using a modified Prime Sieve (aka the Sieve of Eratosthenes): an array that keeps track of the largest prime factor of all the integers in the range of numbers that we care about. Because the maximum serial number is 20,000, it's easy to create an array that big whose values are the largest prime factor of each of its indices.

• Create an array named factor[20000+1] which is initialized to 0.
• Mark factor[1] = 1
• Starting at i=2, loop through each value of the array. If the array value is nonzero, it's not a prime so skip it.
  If the array value is 0, then the index is prime. Mark that index and all its multiples as having that prime index as its biggest factor.

Since we scan the array starting at the smaller integers, marking each prime factor will overwrite smaller primes and the largest factor will be stored.

The factor-marking algorithm runs in approximately O(NlogN) time.

It is now a simple matter to run through each input integer to find the one with the largest factor; this will run in O(N).

#include <stdio.h>
#define MAXN 20000
int factor[MAXN+1];	/* global: init'd to 0 */

main () {
    FILE *fin  = fopen ("bigfact.in", "r");
    FILE *fout = fopen ("bigfact.out", "w");
    int i, j, n, input, bestserial, biggestfactor = 0;

    factor [1] = 1;
    for (i = 2; i <= MAXN; i++) {
	if (factor[i] != 0) continue;
	for (j = i; j <= MAXN; j += i)
	    factor[j] = i;
    }

    fscanf (fin, "%d", &n);
    for (i = 0; i < n; i++) {
	fscanf (fin, "%d", &input);
	if (factor[input] > biggestfactor) {
	    biggestfactor = factor[input];
	    bestserial = input;
	}
    }
    fprintf(fout, "%d\n", bestserial);
    exit (0);
}

This is Poland junior Tomasz Kulczynski's C++ solution to bigfact:

#include <cstdio>
using namespace std;

int max_fact (int x) {
    int i;
    for (i = 2; i*i <= x; i++)
        while ((x%i)!=0 && x > i)
            x /= i;
    return x;
}

int main() {
    freopen ("bigfact.in", "r", stdin);
    freopen ("bigfact.out", "w", stdout);
    int n, ret, i, x, e=-1, y;
    scanf ("%d", &n);
    for (i = 0; i < n; i++) {
        scanf ("%d", &x);
        y = max_fact (x);
        if (y > e) {
            e = y;
            ret = x;
        }
    }
    printf("%d\n",ret);
    return 0;
}

This is USA senior Adam Pantel's Java solution to bigfact:

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

class bigfact {
    public static void main (String [] args) throws IOException {
	RandomAccessFile f = new RandomAccessFile ("bigfact.in", "r");
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("bigfact.out")));
	
	int numCows = Integer.parseInt (f.readLine ());
	int[]all = new int[numCows];
	for (int i = 0; i < numCows; i++) {
	    all[i] = Integer.parseInt (f.readLine ());
	}
	
	int m = 0;
	int m2 =0;
	for (int i = 0; i < all.length; i++) {
	    int j = prFact (all[i]);
	    System.out.println (""+all[i]+" "+j);
	    if (j > m){
		m2 = all[i];
		m = j;
	    }
	}
	out.println (m2);
	out.close ();
	System.exit (0);
    }
    public static int prFact (int x) {
	int m = 1;
	for(int i = 2; i<=x; i++) {
	    if(x % i == 0) {
		m=i;
		while (x%i==0)
		    x =x/i;
	    }
	}
	return m;
    }
}

Here is the Pascal solution for bigfact from freshman Yura Pisarchick of Belarus:

var n, a, an, i, j, w, k, max:integer;
begin
    assign(input, 'bigfact.in');   reset(input);
    assign(output,'bigfact.out'); rewrite(output);
    readln(n);
    for j:=1 to n do begin
	readln(a);
        an:=a;
	w:=trunc(sqrt(a))+1;
	for i:=2 to w do while a mod i=0 do begin
	    if i>max then begin
		max:=i;
		 k:=an;
	    end;
            a:=a div i;
        end;
	if a>max then begin
	    max:=a;
	    k:=an;
	end;
    end;
    writeln(k);
    close(input);
    close(output);
end.