//OPT: -lpthread
#include<thread>
#include<sstream>
#include<iostream>
#include<vector>
#include<atomic>

using namespace std;

typedef long long itype;

// This is not an example of how to calculate primes if you have multiple
// processors.  It is an example of how C++ supports threading in C++11
// (do not use this algorithm for anything other than to chew up CPU time)
bool isprimesub(itype num, itype s, itype e) {
	if (s<2) s=2;
	for(itype x=s;x<e;x++)
		if (num%x==0) return false;
	return true;
}

bool isprime(itype num, int numthread) {
	atomic_flag ans = ATOMIC_FLAG_INIT; // init to clear
	vector<thread> ts;
	for(int i=0;i<numthread;i++)
		ts.emplace_back([i,num,numthread,&ans] {
			if (!isprimesub(num,num*i/numthread,num*(i+1)/numthread))
				ans.test_and_set();
		});
	for(auto &t : ts)
		t.join();
	return !ans.test_and_set();
}


int main(int argc, char **argv) {
	if (argc<2) {
		cerr << "not enough arguments" << endl;
		return 1;
	}
	stringstream ss(argv[1]);
	itype num;
	ss >> num;
	int nthread = 1;
	if (argc>2) {
		stringstream ss(argv[2]);
		ss >> nthread;
	}

	cout << num << (isprime(num,nthread) ? " is prime" : " is not prime") << endl;
}