Finding the intersection of two sets of integers

I need to pass a programming exam in order to graduate but I'm having a hard time passing it because most of my programs are too slow. Can someone give me some tips on how to make my programs faster please? Below is an example of a question we had in the last exam and the code i wrote. My code passed the first test case but for the other 3 it exceeded the time limit. Please let me know if you have any suggestions on how to improve my code.


Description
Given two sets of numbers, output their intersection set.


Input
There are multiple test cases. Each case contains four lines. The first line begins with an integer N. The second line contains N integers, representing the numbers in the first set. The third line has one integer M, and the fourth line contains M integers, represent the numbers in the second set.



All the numbers are 32 bit signed integers.



The input is terminated if N = 0.



For case 1, 1 <= N, M <= 10^3 (Time Limit: 1 sec)

For case 2, 1 <= N, M <= 10^4 (Time Limit: 1 sec)

For case 3, 1 <= N, M <= 10^5 (Time Limit: 1 sec)

For case 4, 1 <= N, M <= 10^6 (Time Limit: 3 sec)



Output
For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two
sets is an empty set, print 「empty」 (without quotes).



Sample Input
3
1 2 3
3
4 5 6
8
4 10 13 8
9 2 1 5
4
4 2 3 1
5
1 2 2 3 2
5
1 2 2 3
1
0



Sample Output
empty
1 2 4
1 2 2 3

This is my code:

```
#include
#include

int set1[2][1000000];
int set2[2][1000000];
int intersection[1000000];

int main()
{
int n;
scanf("%d",&n);

while( n!= 0)
{
int m, i, x, num, y = 0;
int w, u, xx;

for(i = 0; i intersection[i])
{
w = intersection[x];
intersection[x] = intersection[i];
intersection[i] = w;
}
}
}

for(x = 0; x < y;

Let's look at these two nested loops. How many times does the loop body need to be executed?

for(x = 0; x < n; x++)
{
    for(i = 0; i < m; i++)
    {
        /* loop body ... */
    }
}

The loop body gets executed \$ nm \$ times. But the problem statement says that we have \$ 1 \le n, m \le 10^6 \$, so in the worst case \$ n = m = 10^6 \$ and so the loop body gets executed \$ 10^{12} \$ times. There's no way to do that in just 3 seconds!

So you need to find a different algorithm, one that doesn't try to examine every pair of elements.

How might you do that? Well, here are two ideas:

-
Sort the two arrays, and then output the intersection by merging the sorted arrays.

-
Store the first input set in a data structure that has efficient lookup, for example a hash table or a radix tree, and then look up the numbers in the second input set.

StackExchange Code Review Q#91806, answer score: 24