Kind of surprising, my intuitive idea of primes is that they become rarer much faster, while there's really a ton of them.
In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n.
I have a small section about this at https://susam.net/journey-to-prime-number-theorem.html#prime... if you want to read more about this.
See also: https://en.wikipedia.org/wiki/Prime_number_theorem
> In fact, according to the celebrated prime number theorem, the number of primes less than or equal to n is asymptotic to n/log n, which means the density of primes near n is asymptotic to 1/log n.
When written down as a string of digits, log n is another way to say 'proportional to the number of digits'.
The number of digits grows fairly slowly, thus also the 'probability' of a number being prime drops very slowly.
There are more prime numbers than there are squares of integers.
Depends on what you mean by 'hard'. It's easy in the sense that we have algorithms to decide whether a number is prime or composite that take time polynomial in the space it takes to write down your number (ie polynomial in log n).
More from the fact that each prime number makes all its multiples non-prime, so you'd expect this would accumulate quickly in making primes an increasingly rare find. Which is the case, but slower than intuition suggests.
all integers have a square, while not all integers are prime.
in any given span, you'll see more primes than squares, however.
more dense?
That’s true, but I don’t see how that’s an argument. “All integers have a prime ‘the nth prime’, while not all integers are squares” similarly is true, but not an argument as to which set is denser.