List prime-factorized natural numbers up to N in ascending order

Question

For a given n list prime factorization of all natural numbers between 1 and n in ascending order. For example, for n = 10 the output would be:

1:
2: 2^1
3: 3^1
4: 2^2
5: 5^1
6: 2^1 3^1
7: 7^1
8: 2^3
9: 3^2
10: 2^1 5^1

Requirements:

• You cannot just iterate over the numbers and factor each of them. (Unless you know how to factor a number in logarithmic time, and then I doubt you'd be wasting your time solving puzzles.) This is too inefficient.
• The output should be as in the example above: On each line the number and the list of its prime factors.
• Consider that n can be very large, so it might be infeasible to generate all the factorizations into memory and then sort them at the end. (But if you have a clever solution that violates this, post it too.)

Answer 1

C++

Implements a sieve using primes up to sqrt(n). Maintains a list of linked lists to keep track of which primes divide which upcoming numbers. Each time a prime p is used, its Factor structure is moved p slots down the list.

Most of the time is spent in just printfing the answer.

#include <stdio.h>
#include <stdlib.h>

// lists of Factors represent known prime factors of a number                                                                                              
struct Factor {
  Factor(int p) : prime(p), next(NULL) { }
  int prime;
  Factor *next;
};

int main(int argc, char *argv[]) {
  long long n = atoll(argv[1]);

  // figure out the maximum prime we need to sieve with                                                                                                    
  int maxp = 1;
  while ((long long)maxp * maxp < n) maxp++;
  maxp--;

  // find next power of two up from that for our circular buffer size                                                                                      
  int size = 1;
  while (size < maxp) size *= 2;
  int mask = size - 1;

  // allocate circular buffer of lists of sieving prime factors for upcoming numbers                                                                       
  Factor **factors = new Factor*[size]();

  printf("1:\n");

  for (long long x = 2; x < n; x++) {
    Factor *list = factors[x & mask];
    factors[x & mask] = NULL; // reset so it can hold the list for x + size                                                                                

    if (!list && x <= maxp) { // x is a prime we need to sieve with - make new list with just itself                                                       
      list = new Factor(x);
    }

    // print factor list, push each Factor along to the next list.                                                                                         
    printf("%lld:", x);
    long long y = x;
    while (list) {
      Factor *f = list;
      list = f->next;
      int p = f->prime;

      // count how many factors of p are in x                                                                                                              
      int k = 1;
      y /= p;
      while (y % p == 0) {
        k++;
        y /= p;
      }
      printf(" %d^%d", p, k);

      // splice f into the list for the next number it divides                                                                                             
      long long z = x + f->prime;
      f->next = factors[z & mask];
      factors[z & mask] = f;
    }
    // remaining part of x must be prime                                                                                                                   
    if (y != 1) printf(" %lld^1", y);
    printf("\n");
  }
}

Answer 2

Below is my attempt, in R5RS scheme (disclaimer: I'm not actually a Schemer (yet!), so pardon the (probably) terrible code).

(define count 10)

; `factors` is our vector of linked-lists of factors.  We're adding to these
; as we go on.
(define factors (make-vector count 'not-found))
(vector-set! factors 0 '())

; `primes-so-far` contains all the prime numbers we've discovered thus far.
; We use this list to speed up the dividing of numbers.
;   `primes-so-far-last` is a ref to the last entry in the `primes-so-far`
; list, for O(1) appending to the list.
(define primes-so-far '(dummy))
(define primes-so-far-last primes-so-far)

;; Helpers
(define (factor-ref n)
  (vector-ref factors (- n 1)))

(define (factor-cached? n)
  (not (eq? (vector-ref factors (- n 1)) 'not-found)))

(define (factor-put n factor)
  (let* ((rest        (/ n factor))
         (factor-cell (cons factor (factor-ref rest))))
    (vector-set! factors (- n 1) factor-cell)
    factor-cell))

(define (prime-append n)
  (let ((new-prime-cell (cons n '())))
    (set-cdr! primes-so-far-last new-prime-cell)
    (set!     primes-so-far-last new-prime-cell)
    new-prime-cell))

;; The factor procedure (assumes that `[1..n-1]` have already been factorized).
(define (factor n)
  (define (divides? m n)
    (= (modulo n m) 0))

  ; n       the number to factor.
  ; primes  the list of primes to try to divide with.
  (define (iter n primes)
    (cond ((factor-cached? n)
           (factor-ref n))

          ((null? primes)
           ; no primes left to divide with; n is prime.
           (prime-append n)
           (factor-put n n)) ; the only prime factor in a prime is itself

          ((divides? (car primes) n)
           (factor-put n (car primes))
           (factor-ref n))

          (else
           (iter n (cdr primes)))))

  (iter n (cdr primes-so-far)))

(define (print-loop i)
  (if (<= i count)
      (begin
        (display i)
        (display ": ")
        (display (factor i))
        (newline)
        (print-loop (+ i 1)))))

(print-loop 1)

Prints as:

1: ()
2: (2)
3: (3)
4: (2 2)
5: (5)
6: (2 3)
7: (7)
8: (2 2 2)
9: (3 3)
10: (2 5)

(Not exactly like in the task description, but all you'd have to do to get that output is to fold the list and merge repetitions of the same number, during the output part of the code. The internal representation/algorithm would still be the same.)

The idea is to cache the previously computed values, but make use of the fact that the factors of n is the first prime factor of n and the prime factors of (n / first-factor). But the latter is already known, so we just re-use the already existing list of factors for that smaller number. Thus, for each number in [1..n] which is not prime, a single cons cell is stored.

For each number, a single cons cell is created and stored. Thus, this approach should run with O(n) storage usage. I've no clue if it's possible to neatly express the time-complexity.

Answer 3

Rust

Rust port of @Keith Randall's C++ code.

use std::env;

#[derive(Clone)]
struct Factor {
    prime: i32,
    next: Option<Box<Factor>>,
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        eprintln!("Usage: {} <number>", args[0]);
        std::process::exit(1);
    }

    let n: i64 = args[1].parse().expect("Invalid number");

    // figure out the maximum prime we need to sieve with
    let mut maxp: i64 = 1;
    while (maxp * maxp) < n {
        maxp += 1;
    }
    maxp -= 1;

    // find next power of two up from that for our circular buffer size
    let mut size = 1;
    while (size as i64) < maxp {
        size *= 2;
    }
    let mask = (size - 1) as i64;

    // allocate circular buffer of lists of sieving prime factors for upcoming numbers
    let mut factors: Vec<Option<Box<Factor>>> = vec![None; size];

    println!("1:");

    for x in 2..n {
        let idx = (x & mask) as usize;
        let mut list = factors[idx].take(); // take ownership and reset slot for next pass

        // if no list and x <= maxp, this x is prime and needs to be used to sieve
        if list.is_none() && x <= maxp {
            list = Some(Box::new(Factor {
                prime: x as i32,
                next: None,
            }));
        }

        // print factor list, push each Factor along to the next list.
        print!("{}:", x);
        let mut y = x;
        let mut current_list = list;
        while let Some(mut f) = current_list {
            let p = f.prime as i64;
            current_list = f.next.take();

            // count how many factors of p are in x
            let mut k = 1;
            y /= p;
            while y % p == 0 {
                k += 1;
                y /= p;
            }
            print!(" {}^{}", p, k);

            // splice f into the list for the next number it divides
            let z = x + p;
            let zidx = (z & mask) as usize;
            f.next = factors[zidx].take();
            factors[zidx] = Some(f);
        }

        // if there's a remaining prime factor not in the list
        if y != 1 {
            print!(" {}^1", y);
        }
        println!();
    }
}

Attempt This Online!

Answer 4

C (gcc)

#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

int square(int a){
	return a * a;
}

void prime_factors(int n){
	// this is an array of n elements, which will contain all found primes.
	// curprime stores the index of the last found prime, which saves us searching for where to insert the next one and things.
	int* primes = calloc(sizeof(int), n);
	int curprime = 0;

	printf("1:\n"); // Micro optimization, and rids me of the messing around that is 1.
	for(int i=2; i<=n; i++){
		// Print the current i.
		printf("%i: ",i);

		// Define val, which we'll slowly make smaller and smaller. Mwahaha.
		int val = i;
		int isprime = true;	// This will be set to false if it's divisible by any primes, which of course, means it's also not a prime.

		// Loop through primes, this loop stops if we've reached either more than sqrt(count) primes, or val is equal to zero (as such, it's fully prime factorized).
		for(int*prime_pointer = primes; val && square((int)(prime_pointer-primes)) < curprime; prime_pointer++){
			int prime = *prime_pointer;
			// if the current val is divisible by the current prime.
			while(val%prime == 0){
				isprime = false; 	// We know that this number isn't prime.
				val = val / prime;	// Divide val by it.
				printf("%i ",prime);// And write this prime.
			}
		}
		if(isprime){	// If this number is a prime.
			printf("%i ",i);	// Append it to its own list.
			primes[curprime++] = i;	// And append this new prime to our list of primes.
		}
		printf("\n");	// Terminate the line with a newline. Duh...
	}
}

int main(int argc, char** argv){
	prime_factors(1000);
}

Defines the function prime_factors which takes an integer n and outputs via printf in the following format:

1:
2: 2 
3: 3 
4: 2 2 
5: 5 
6: 2 3 
7: 7 
8: 2 2 2 
9: 3 3 
10: 2 

This uses O(n) extra memory, and I'm not sure the time complexity.

Try it online!