Skip to content

Instantly share code, notes, and snippets.

@chermehdi
Created June 8, 2017 15:28
Show Gist options
  • Save chermehdi/3487f7de4b256ff1ee17b8382ff62bda to your computer and use it in GitHub Desktop.
Save chermehdi/3487f7de4b256ff1ee17b8382ff62bda to your computer and use it in GitHub Desktop.
for each given N find it's prime factors problem propsed in scorify challange .
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int nextInt(){
int a; scanf("%d", &a); return a;
}
int nextLong(){
long long a; scanf("%lld", &a); return a;
}
int m, n;
const int N = 1e5 + 10;
int main() {
int seive[N];
int list[1000];
/* the pre processing part */
seive[1] = 1;
for (int i = 2; i < N; i++)
seive[i] = i;
for (int i = 4; i < N; i += 2)
seive[i] = 2;
for (int i = 3; i * i < N; i++) {
if (seive[i] == i) {
for (int j = i * i; j < N; j += i)
if (seive[j] == j)
seive[j] = i;
}
}
int t = nextInt();
/* answer queries in O(log(N)) per query */
for (int tc = 1; tc <= t; tc++){
n = nextInt();
int j = 0;
while (n != 1) {
list[j++] = (seive[n]);
n = n / seive[n];
}
for(int i = 0; i < j; i++){
if(i > 0) printf(" ");
printf("%d", list[i]);
}
printf("\n");
}
return 0;
}
@Eroui
Copy link

Eroui commented Jun 8, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment