pub mod primes {
    
	pub fn sieve_of_atkin(input: i64) -> Vec<i64> {
		// Input number
		let max = input as usize;

		let root:i64 = (max as f64).sqrt().ceil() as i64;
		// yoyo vectors
		let mut sieve: Vec<bool> = Vec::with_capacity(max);
		let mut primes: Vec<i64> = Vec::with_capacity((max / 2 + 1) as usize);

		let mut insert: i64 = 2;

		let mut items_pushed = 0;

		loop {
		sieve.push(false);
		items_pushed += 1;
		if items_pushed == max { break; }
		}
		items_pushed = 0;
		loop {
			primes.push(0);
			items_pushed += 1;
			if items_pushed == (max / 2 + 1) { break; }
		}

		primes[0] = 2;
		primes[1] = 3;

		for x in 1..root+1 {
			for y  in 1..root+1 {
				let mut n = 4*x*x + y*y;
				if (n as i64) < (max as i64) && (n % 12 == 1 || n % 12 == 5) {
					sieve[n as usize] ^= true;
				}
				n = 3*x*x + y*y;
				if (n as i64) <= (max as i64) && n % 12 == 7 {
					sieve[n as usize] ^= true;
				}
				n = 3*x*x - y*y;
					if (x as i64) > (y as i64) && (n as i64) <= (max as i64) && n % 12 == 11 {
					sieve[n as usize] ^= true;
				}
			}
		}

		for r in 5..root+1 {
			if sieve[r as usize] {
				let mut i = r*r;
				while i < max as i64 {
					sieve[i as usize] = false;
					i += r*r;
				}
			}
		}

		for a in 5..max {
			if sieve[a] {
				primes[insert as usize] = a as i64;
				insert += 1;
			}
		}

		return primes.into_iter().filter(|&x| x != 0).collect::<Vec<_>>();
	}
}