어떤 자연수 n 이 소수인지 구할때, n 이 작을 경우에는 다음과 같은 방법을 사용한다. 

1. Trial Division 
소수의 성질을 이용, 어떤 수 n 이 소수인지 판별하기 위해 n 을 2 부터 n-1 까지 하나씩 나누어보아 나누어 떨어지는 수가 존재하지 않으면 n 은 소수가 된다.

Notes 
- 2를 제외한 모든 소수는 홀수이므로, 어떤 수 n 이 짝수이면 소수가 아니다. 
- 만약 N 이 합성수라면 N = a*b 형태가 되므로 ( a > 1 && b > 1 ), a 와 b 둘 중 하나는 sqrt(N) 보다 작거나 같음을 알 수 있다. 그러므로 N 을 2부터 sqrt(N) 까지 나눠보아 나누어지지 않으면 N 은 소수가 된다. 

2. 에라토스테네스의 체(Sieve of Eratosthenes)
n 이 작을 때 ( 일반적으로 n <= 10,000,000 ) 2 부터 n 까지의 소수를 찾는 가장 효율적인 방법으로 알려져 있다. 어떤 수 P 가 소수이면 P 로 나눌 수 있는 P 의 배수들은 소수가 아닌 것으로 체크한다. 이러한 과정을 반복하면서 주어진 [2,n] 구간 내에서 소수를 찾아낸다.

소수일 것 같은 수 (Probable Prime) 판별법 
어떤 자연수 n 이 소수인지 아닌지 판별할 때, n 이 매우 커지면 유한시간내에 n 이 소수인지 판별하기 곤란해지게 된다. 이 때문에 n 의 소수 여부를 판별하는 근사해를 구하는 검사법이 여럿 개발되었는데, 이 검사법에 의해 n 이 합성수가 아님이 판별되는 경우에 n 을 소수일 것 같다 (Probable Prime) 고 한다. 
Probable Prime (PRP) 의 정의는, 소수가 갖는 특정 상태를 만족하는 자연수이다. 

1. Wheel Factorization 
소수의 특징 중 하나인 [2,n] 구간내에 존재하는 소수의 갯수는 n 이 커질 수록 분포도가 희박해진다는 점에서 착안한 방법. 에라토스테네스의 체의 특수한 응용방법이다. 기본 원리는 에라토스테네스의 체와 동일하나, 구간내의 모든 소수에 대해 배수를 찾아 검사하는 것이 아니라 몇개의 소수를 가지고 이 수들로 나누어지는 수들을 걸러내는 방식으로 구하는 것이 차이점이다. 소수 2, 3을 가지고 Wheel Factorization 을 한다면, 우선 2와 3 의 배수를 모두 소수가 아닌 것으로 판별한다. 그리고 그 다음 소수인 5, 7 를 이용해 또다시 이 작업을 반복한다. 
일반적으로 많이 쓰는 factorization 은 6N+1, 6N+5 를 사용하여 주어진 구간 [1,n] 내에서 나누어 지지 않는 수를 소수일 것 같은 수로 판별한다. ( Wheel Factorization 은 n 이 커질수록 정확도가 떨어지므로 이를 위해 n 이 커질수록 더 많은 소수를 이용해 나누어보아야 한다. )

 
 for all  

Probable Prime 판별법은 이외에도 여러가지가 개발되어 있다. 


참고1
임의의 큰 자연수를 소인수분해하는 문제는 NP 문제로 알려져 있다. 
거대한 합성수의 소인수분해는 암호문 해독에 응용되어, 기존의 암호문 전달 체계와 다른 암호학에 공공열쇠 개념을 도입하여 리베스트(Ron Rivest)와, 샤미르(Adi shamir), 아들만(Len Adleman)의 이름을 딴 RSA방식이라는 암호이론이 개발되기도 했다.
http://mathworld.wolfram.com/PrimalityTest.html


참고2 - 관련 사이트 
TopCoder Tutorial : Primality Test - Non Deterministic Algorithms
Wikipedia

파일 상태를 읽으려면

• CFile 클래스를 사용하여 파일 정보를 읽고 설정합니다. CFile 정적 멤버 함수인 GetStatus를 사용하여 파일의 존재 여부를 확인할 수 있습니다. 지정된 파일이 존재하지 않으면 GetStatus가 0을 반환합니다.

따라서 GetStatus 결과를 사용하여 다음 예제와 같이 파일을 열 때 CFile::modeCreate 플래그의 사용 여부를 결정할 수 있습니다.

CFile theFile;
char* szFileName = "c:\\test\\myfile.dat";
BOOL bOpenOK;

CFileStatus status;
if( CFile::GetStatus( szFileName, status ) )
{
    // Open the file without the Create flag
    bOpenOK = theFile.Open( szFileName, 
                    CFile::modeWrite );
}
else
{
    // Open the file with the Create flag
    bOpenOK = theFile.Open( szFileName, 
                    CFile::modeCreate | CFile::modeWrite );
}

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<root>
   <ApplicationSettings
           option_a = "10"
           option_b = "24"
           >
   </ApplicationSettings>
   <OtherStuff
           option_x = "500"
           >
   </OtherStuff>
</root>

#ifndef XML_PARSER_HPP
#define XML_PARSER_HPP
/**
 *  @file
 *  Class "GetConfig" provides the functions to read the XML data.
 *  @version 1.0
 */
#include <xercesc/dom/DOM.hpp>
#include <xercesc/dom/DOMDocument.hpp>
#include <xercesc/dom/DOMDocumentType.hpp>
#include <xercesc/dom/DOMElement.hpp>
#include <xercesc/dom/DOMImplementation.hpp>
#include <xercesc/dom/DOMImplementationLS.hpp>
#include <xercesc/dom/DOMNodeIterator.hpp>
#include <xercesc/dom/DOMNodeList.hpp>
#include <xercesc/dom/DOMText.hpp>

#include <xercesc/parsers/XercesDOMParser.hpp>
#include <xercesc/util/XMLUni.hpp>

#include <string>
#include <stdexcept>

// Error codes

enum {
   ERROR_ARGS = 1, 
   ERROR_XERCES_INIT,
   ERROR_PARSE,
   ERROR_EMPTY_DOCUMENT
};

class GetConfig
{
public:
   GetConfig();
  ~GetConfig();
   void readConfigFile(std::string&) throw(std::runtime_error);
 
   char *getOptionA() { return m_OptionA; };
   char *getOptionB() { return m_OptionB; };

private:
   xercesc::XercesDOMParser *m_ConfigFileParser;
   char* m_OptionA;
   char* m_OptionB;

   // Internal class use only. Hold Xerces data in UTF-16 SMLCh type.

   XMLCh* TAG_root;

   XMLCh* TAG_ApplicationSettings;
   XMLCh* ATTR_OptionA;
   XMLCh* ATTR_OptionB;
};
#endif

#include <string>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <list>

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <errno.h>

#include "parser.hpp"

using namespace xercesc;
using namespace std;

/**
 *  Constructor initializes xerces-C libraries.
 *  The XML tags and attributes which we seek are defined.
 *  The xerces-C DOM parser infrastructure is initialized.
 */

GetConfig::GetConfig()
{
   try
   {
      XMLPlatformUtils::Initialize();  // Initialize Xerces infrastructure
   }
   catch( XMLException& e )
   {
      char* message = XMLString::transcode( e.getMessage() );
      cerr << "XML toolkit initialization error: " << message << endl;
      XMLString::release( &message );
      // throw exception here to return ERROR_XERCES_INIT
   }

   // Tags and attributes used in XML file.
   // Can't call transcode till after Xerces Initialize()
   TAG_root        = XMLString::transcode("root");
   TAG_ApplicationSettings = XMLString::transcode("ApplicationSettings");
   ATTR_OptionA = XMLString::transcode("option_a");
   ATTR_OptionB = XMLString::transcode("option_b");

   m_ConfigFileParser = new XercesDOMParser;
}

/**
 *  Class destructor frees memory used to hold the XML tag and 
 *  attribute definitions. It als terminates use of the xerces-C
 *  framework.
 */

GetConfig::~GetConfig()
{
   // Free memory

   delete m_ConfigFileParser;
   if(m_OptionA)   XMLString::release( &m_OptionA );
   if(m_OptionB)   XMLString::release( &m_OptionB );

   try
   {
      XMLString::release( &TAG_root );

      XMLString::release( &TAG_ApplicationSettings );
      XMLString::release( &ATTR_OptionA );
      XMLString::release( &ATTR_OptionB );
   }
   catch( ... )
   {
      cerr << "Unknown exception encountered in TagNamesdtor" << endl;
   }

   // Terminate Xerces

   try
   {
      XMLPlatformUtils::Terminate();  // Terminate after release of memory
   }
   catch( xercesc::XMLException& e )
   {
      char* message = xercesc::XMLString::transcode( e.getMessage() );

      cerr << "XML ttolkit teardown error: " << message << endl;
      XMLString::release( &message );
   }
}

/**
 *  This function:
 *  - Tests the access and availability of the XML configuration file.
 *  - Configures the xerces-c DOM parser.
 *  - Reads and extracts the pertinent information from the XML config file.
 *
 *  @param in configFile The text string name of the HLA configuration file.
 */

void GetConfig::readConfigFile(string& configFile)
        throw( std::runtime_error )
{
   // Test to see if the file is ok.

   struct stat fileStatus;

   int iretStat = stat(configFile.c_str(), &fileStatus);
   if( iretStat == ENOENT )
      throw ( std::runtime_error("Path file_name does not exist, or path is an empty string.") );
   else if( iretStat == ENOTDIR )
      throw ( std::runtime_error("A component of the path is not a directory."));
   else if( iretStat == ELOOP )
      throw ( std::runtime_error("Too many symbolic links encountered while traversing the path."));
   else if( iretStat == EACCES )
      throw ( std::runtime_error("Permission denied."));
   else if( iretStat == ENAMETOOLONG )
      throw ( std::runtime_error("File can not be read\n"));

   // Configure DOM parser.

   m_ConfigFileParser->setValidationScheme( XercesDOMParser::Val_Never );
   m_ConfigFileParser->setDoNamespaces( false );
   m_ConfigFileParser->setDoSchema( false );
   m_ConfigFileParser->setLoadExternalDTD( false );

   try
   {
      m_ConfigFileParser->parse( configFile.c_str() );

      // no need to free this pointer - owned by the parent parser object
      DOMDocument* xmlDoc = m_ConfigFileParser->getDocument();

      // Get the top-level element: NAme is "root". No attributes for "root"
      
      DOMElement* elementRoot = xmlDoc->getDocumentElement();
      if( !elementRoot ) throw(std::runtime_error( "empty XML document" ));

      // Parse XML file for tags of interest: "ApplicationSettings"
      // Look one level nested within "root". (child of root)

      DOMNodeList*      children = elementRoot->getChildNodes();
      const  XMLSize_t nodeCount = children->getLength();

      // For all nodes, children of "root" in the XML tree.

      for( XMLSize_t xx = 0; xx < nodeCount; ++xx )
      {
         DOMNode* currentNode = children->item(xx);
         if( currentNode->getNodeType() &&  // true is not NULL
             currentNode->getNodeType() == DOMNode::ELEMENT_NODE ) // is element 
         {
            // Found node which is an Element. Re-cast node as element
            DOMElement* currentElement
                        = dynamic_cast< xercesc::DOMElement* >( currentNode );
            if( XMLString::equals(currentElement->getTagName(), TAG_ApplicationSettings))
            {
               // Already tested node as type element and of name "ApplicationSettings".
               // Read attributes of element "ApplicationSettings".
               const XMLCh* xmlch_OptionA
                     = currentElement->getAttribute(ATTR_OptionA);
               m_OptionA = XMLString::transcode(xmlch_OptionA);

               const XMLCh* xmlch_OptionB
                     = currentElement->getAttribute(ATTR_OptionB);
               m_OptionB = XMLString::transcode(xmlch_OptionB);

               break;  // Data found. No need to look at other elements in tree.
            }
         }
      }
   }
   catch( xercesc::XMLException& e )
   {
      char* message = xercesc::XMLString::transcode( e.getMessage() );
      ostringstream errBuf;
      errBuf << "Error parsing file: " << message << flush;
      XMLString::release( &message );
   }
}

#ifdef MAIN_TEST
/* This main is provided for unit test of the class. */

int main()
{
   string configFile="sample.xml"; // stat file. Get ambigious segfault otherwise.

   GetConfig appConfig;

   appConfig.readConfigFile(configFile);

   cout << "Application option A="  << appConfig.getOptionA()  << endl;
   cout << "Application option B="  << appConfig.getOptionB()  << endl;

   return 0;
}
#endif

 // Initialize the XML4C2 system.
   try
   {
       XMLPlatformUtils::Initialize();
   }

   catch(const XMLException& toCatch)
   {
       char *pMsg = XMLString::transcode(toCatch.getMessage());
       XERCES_STD_QUALIFIER cerr << "Error during Xerces-c Initialization.\n"
            << "  Exception message:"
            << pMsg;
       XMLString::release(&pMsg);
       return 1;
   }

1.  XML 생성하기  

DOMImplementation* impl =
  DOMImplementationRegistry::getDOMImplementation(X("Core"));

//(Root )노드 생성 
DOMDocument* doc = impl->createDocument(
         0,                    // root element namespace URI.
         X(”company”),   // root element name
         0);                   // document type object (DTD).

DOMElement* rootElem = doc->getDocumentElement();  

// node 생성와 값에 대한 값을 넣는다.
// 노드 생성
DOMElement*  prodElem = doc->createElement(X(”product”));
rootElem->appendChild(prodElem);

// 그 노드에 맞는 값
DOMText*    prodDataVal = doc->createTextNode(X(”Xerces-C”));
          prodElem->appendChild(prodDataVal);

2. 생성한 XML 파일로 저장하기.  

static XMLCh*  gOutputEncoding = 0;

DOMWriter  *theSerializer = ((DOMImplementationLS*)impl)->createDOMWriter();

// set user specified output encoding
theSerializer->setEncoding(gOutputEncoding);
XMLFormatTarget *myFormTarget;

myFormTarget = new LocalFileFormatTarget(”c://output.xml”);

theSerializer->writeNode(myFormTarget, *doc);  
3. 이미 생성된 XML 파일 검색하기  

// 이미 기본 설정한거라 보고…다운받으면 그 안에 소스가 존재합니다. 참고 바람.
// 외부 파일을 가져온다.
parser->resetDocumentPool();
doc = parser->parseURI(xmlFile);

// 파일을 검색할때는 재귀가 기본이다.

// DOMNode *n

if (n->getNodeType() == DOMNode::ELEMENT_NODE)

{

    // 노드의 이름 가져온다.
    char *name =  XMLString::transcode(n->getNodeName());

    // 노드에 대한 값을 가져온다.
    char* nodeValue = XMLString::transcode (n->getFirstChild()->getNodeValue ());

    // 속성
   if(n->hasAttributes()) {

        DOMNamedNodeMap *pAttributes = n->getAttributes();
        int nSize = pAttributes->getLength();

        // 한 노드에 붙어있는 모든 속성과 값을 가져온다.
        for(int i=0; nSize>i; i++){  
                   DOMAttr *pAttributeNode = (DOMAttr*) pAttributes->item(i);
                   // get attribute name
                   char *name = XMLString::transcode(pAttributeNode->getName());
                  
                   XERCES_STD_QUALIFIER cout << "Attribute Name : " << name << " -> “;
                   XMLString::release(&name);
                  
                   // get attribute type
                   name = XMLString::transcode(pAttributeNode->getValue());
                   XERCES_STD_QUALIFIER cout << “Attribute Value : “<< name << XERCES_STD_QUALIFIER endl;
                   XMLString::release(&name);
               }
   }
}