Coulomb interaction, following an inverse-square force-law, quantifies the amount of force between two stationary, electrically charged particles. The long-range nature of Coulomb interactions poses a major challenge to molecular dynamics simulations which are major tools for problems at the nano-/micro- scale. Various algorithms aim to speed up the pairwise Coulomb interactions to a linear scaling but the poor scalability limits the size of simulated systems. Here, we conduct an efficient molecular dynamics algorithm with the random batch Ewald method on all-atom systems where the complete Fourier components in the Coulomb interaction are replaced by randomly selected mini batches. By simulating the N-body systems up to 100 million particles using 10 thousand CPU cores, we show that this algorithm furnishes O(N) complexity, almost perfect scalability and an order of magnitude faster computational speed when compared to the existing state-of-the-art algorithms. Further examinations of our algorithm on distinct systems, including pure water, micro-phase-separated electrolyte and protein solution demonstrate that the spatiotemporal information on all time and length scales investigated and thermodynamic quantities derived from our algorithm are in perfect agreement with those obtained from the existing algorithms. Therefore, our algorithm provides a breakthrough solution on scalability of computing the Coulomb interaction. It is particularly useful and cost-effective to simulate ultra-large systems, which was either impossible or very costing to conduct using existing algorithms, thus would benefit the broad community of sciences.