枚举素数，时间超出限制。(关于埃式筛法)

问题遇到的现象和发生背景

                                                                                                             《新朋友》
   新学期到了，信息学社团准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。
        输入格式:

一个正整数N（1<N<32768），表示会员人数。

输出格式:

一个整数，表示新朋友的人数。
限制:

空间限制：128MByte
时间限制：1秒
样例:

输入：

25608
输出：

7680
问题枚举时间过长，时间超限

问题相关代码，请勿粘贴截图

//我写的代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const int maxn = 32770;
int mp[maxn];
 
int main()
{
    int T, n;
    scanf("%d",&T);
    while(T--)
    {
        memset(mp, 0, sizeof mp);
        scanf("%d",&n);
        for( int i = 2; i < n; i++ )
        {
            if( n % i == 0 )
            {
                for( int j = 1; i*j < n; j++ )
                {
                    mp[i*j] = 1;
                }
            }
        }
        int sum = 0;
        for( int i = 1; i < n; i++ )
        {
            if( !mp[i] )
                sum++;
        }
        printf("%d\n", sum);
    }
    return 0;
}

运行结果及报错内容

输出超限
语言：C++
用时: 196 ms 内存: 2212 kb 代码长度: 711
测试数据
测试点编号 结果 内存 耗时
1 OLE 2212k 196ms

我的解答思路和尝试过的方法

我想要达到的结果

缩短到标准时间

这个题有缺陷吧？题目只是说和会长是老朋友的，那么一定有公约数；但有公约数的，不一定是老朋友吧
//
for( int i = 2; i < n; i++ )这个循环效率不高，改为
int k = sqrt(n);
for( int i = 2; i<=k; i++ )
i>k的情况肯定不是质因数了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const int maxn = 32770;
int mp[maxn];
 
int main()
{
    int T, n;
    
        memset(mp, 0, sizeof mp);
        scanf("%d",&n);
        for( int i = 2; i < n; i++ )
        {
            if( n % i == 0 )
            {
                for( int j = 1; i*j < n; j++ )
                {
                    mp[i*j] = 1;
                }
            }
        }
        int sum = 0;
        for( int i = 1; i < n; i++ )
        {
            if( !mp[i] )
                sum++;
        }
        printf("%d\n", sum);
    
    return 0;
    
    
    
}