Viết chương trình, nhập vào một số tự nhiên n và in ra tất cả các số nguyên tố nhỏ hơn n

Viết chương trình, nhập vào một số tự nhiên n và in ra tất cả các số nguyên tố nhỏ hơn n (n<1000000) Mình cần cả chương trình và giải thích bài làm, cảm ơn mọi người