This is a technicality, but isn't it the case that if the deterministic algorithm required takes up as much space at the mathematical object itself, the object can be considered random?(according to Gregory Chaitin etc.)

https://en.m.wikipedia.org/wiki/Algorithmically_random_seque...

That is one sense of the concept "random", but the primes are trivially disqualified from that (please forgive my coffeescript):

  $ wc -c primes.coffee
  110 primes.coffee
  $ cat primes.coffee 
  ps=[n=2]
  until ps.join(',').length>110
    n++
    ps.push n unless ps.some (p)->not(n%p)
  console.log ps.join ','
  $ coffee primes.coffee | wc -c
  115
  $ coffee primes.coffee 
  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151